정렬 알고리즘 C++ 구현

정렬 알고리즘을 C++으로 구현해보자.

 

 

선택정렬

 

#include <bits/stdc++.h>
using namespace std;
int a[100000];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
        
    for (int i = n - 1; i > 0; i--)
        swap(*max_element(a, a + i + 1), a[i]);
    
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
}

 

선택정렬 (재귀)

 

#include <bits/stdc++.h>
using namespace std;
int a[100000];
 
void selection(int n) {
    if (n == 1) return;
    swap(*max_element(a, a + n), a[n - 1]);
    selection(n - 1);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    selection(n);
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
}

버블정렬

 

#include <bits/stdc++.h>
using namespace std;
int a[100000];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
 
    for (int i = n - 1; i >= 1; i--)
        for (int j = 0; j < i; j++)
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
 
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
}

 

삽입정렬 

 

#include <bits/stdc++.h>
using namespace std;
int a[100000];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
 
    for (int i = 1; i < n; i++) {
        int t = a[i];
        int j;
        for (j = i - 1; j >= 0; j--) {
            if (t < a[j]) a[j + 1] = a[j];
            else break;
        }
        a[j + 1] = t;
    }
 
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
}

 

#include <bits/stdc++.h>
using namespace std;
int a[100002], b[100002];
 
void merge(int x, int y) {
    int m = (x + y) / 2;
    int s = x, e = m + 1;
    int k = x;
    while (s <= m && e <= y) {
        if (a[s] < a[e]) b[k++] = a[s++];
        else b[k++] = a[e++];
    }
    while (s <= m) b[k++] = a[s++];
    while (e <= y) b[k++] = a[e++];
    for (int i = x; i <= y; i++) a[i] = b[i];
}
 
void mergeSort(int x, int y) {
    if (x < y) {
        mergeSort(x, (x + y) / 2);
        mergeSort((x + y) / 2 + 1, y);
        merge(x, y);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    mergeSort(1, n);
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
}

#include <bits/stdc++.h>
using namespace std;
int a[100001];
 
int Partition(int x, int y) {
    int s = x, e = x, p = a[y];
    for (; e < y; e++)
        if (a[e] < p) swap(a[s++], a[e]);
    swap(a[s], a[y]);
    return s;
}
 
void quickSort(int x, int y) {
    if (x < y) {
        int p = Partition(x, y);
        quickSort(x, p - 1);
        quickSort(p + 1, y);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    quickSort(1, n);
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
}

#include <bits/stdc++.h>
using namespace std;
int a[100001], n;
 
void heapify(int x, int e) {
    int l = 2 * x, r = 2 * x + 1;
    int minx;
    if (r <= e) minx = a[l] < a[r] ? l : r;
    else if (l <= e) minx = l;
    else return;
    if (a[x] > a[minx]) {
        swap(a[x], a[minx]);
        heapify(minx, e);
    }
}
 
void buildHeap(int x) {
    for (int i = x / 2; i >= 1; i--)
            heapify(i, n);
}
 
void heapSort(int x) {
    buildHeap(x);
    for (int i = n; i > 0; i--) {
        cout << a[1] << ' ';
        swap(a[1], a[i]);
        heapify(1, i - 1);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    heapSort(n);
}

 

 

계수정렬

 

#include <iostream>
using namespace std;
int a[100001];
int main() {
    int n, t;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t;
        a[t]++;
    }
    for (int i = 0; i <= 100000; i++) {
        for (int j = 0; j < a[i]; j++)
            cout << i << ' ';
    }
}