정렬(Sorting)

1. 선택정렬(Selection Sort)

2. 버블 정렬(Bubble Sort)

3. 삽입 정렬(Insertion Sort)

4. 합병 정렬(Merge Sort)

5. 퀵 정렬(Quick Sort)

참고

• In-Place 알고리즘: 입력 배열 이외의 추가적인 메모리가 필요없는 알고리즘

• On/Off-line 알고리즘: 정렬 중 추가로 데이터가 들어올 수 있/없는 알고리즘

• Stable Sort: 중복된 키를 순서대로 정렬하는 정렬 알고리즘

---

1.선택 정렬(Selection Sort)

Time Complexity
- Best O(n²)
- Avg O(n²)
- Worst O(n²)
In-Place Algorithm
Off-line Algorithm
Unstable Sort

주어진 배열에서 최소값을 찾아서 앞으로 갖다 놓는 알고리즘.

배열의 원소를 하나씩 차례대로 보면서 비교하기 때문에 O(n²)로 성능은 별로 좋지 않지만 구현이 몹시 간단하다.

void selectionSort() {
    int minIndex;
    int arry[10] = { 10, 4, 6, 3, 2, 7, 1, 9, 8, 5 };

    for (int i = 0; i < 10; i++) {
        minIndex = i;
        for (int j = i + 1; j < 10; j++) {
            if (arry[j] < arry[minIndex])
                minIndex = j;
        }
        swap(arry[i], arry[minIndex]);
    }

    for (int i = 0; i < 10; i++)
        cout << arry[i] << ' ';
}

minIndex에 i를 집어 넣고, i+1부터 체크하면서 minIndex에 있는 원소보다 j에 있는 원소가 작으면 minIndex를 j로 바꿔준다.

배열 한 번을 다 보면 i에 있는 원소와 minIndex에 있는 원소를 바꿔주면 끝!

인덱스가 아닌 값을 체크하면 더 편하다.

for (int i = 0; i < 10; i++)
      for (int j = i + 1; j < 10; j++)
         if (arry[i] > arry[j]) swap(arry[i], arry[j]);

2. 버블 정렬(Bubble Sort)

Time Complexity
- Best O(n2)
- Avg O(n²)
- Worst O(n²)
In-Place Algorithm
Off-line Algorithm
Stable Sort

원소들을 하나씩 보면서 바로 옆에 있는 원소들을 비교해서 바꿔준다. 거품 보글보글처럼 바뀌어서 버블 정렬이다!

얘도 배열에 있는 원소를 차례대로 보면서 바꾸기 때문에 시간복잡도가 O(n²) 이다.

void bubbleSort {
    int arry[10] = { 10, 4, 6, 3, 2, 7, 1, 9, 8, 5 };

    for (int i = 0; i < 10; i++) 
        for (int j = 1; j < 10-i; j++) 
            if (arry[j] < arry[j - 1]) swap(arry[j], arry[j - 1]);

    for (int i = 0; i < 10; i++)
        cout << arry[i] << ' ';
}

arry[j]와 arry[j-1] 이렇게 인접한 두 원소를 비교해가면서 차례대로 봐준다.

바깥의 반복문이 한 번 돌 때마다 가장 큰 수가 가장 끝에 가기 때문에 하나씩 덜 봐주면 된다j < 10-i.

3. 삽입 정렬(Insertion Sort)

Time Complexity
- Best O(n)
- Avg O(n²)
- Worst O(n²)
In-Place Algorithm
On-line Algorithm
Stable Sort

key를 찾아서 똑하고 떼와서 알맞은 위치에 삽입하는 알고리즘이다.

Worst case는 역순인 경우, O(n²)가 된다.

void InsertionSort() {
    int key;
    int arry[10] = { 10, 4, 6, 3, 2, 7, 1, 9, 8, 5 };

    for (int i = 1; i < 10; i++) {
        key = arry[i];
        for (int j = i - 1; j >= 0 && arry[j] > key; j--)
            arry[j + 1] = arry[j];

        arry[j + 1] = key;
    }

    for (int i = 0; i < 10; i++)
        cout << arry[i] << ' ';
}

맨 앞 친구를 놔두고 첫번째 원소를 key로 두고 시작한다.

key랑 key의 앞에 있는 친구들과 비교해서 작으면 계속해서 바꿔준다.

여기까지의 알고리즘은 구현하기 쉽지만 비효율적이다!

---

 

 

4. 합병 정렬(Merge Sort)

Time Complexity
- Best O(nlogn)
- Avg O(n log n)
- Worst O(n log n)
Not In-Place Algorithm
Off-line Algorithm
Stable Sort

분할 정복(Divide & Conquer) 방법이 적용된 대표적인 알고리즘.

합칠 때 별도의 배열 공간이 필요하기 때문에 In-Place하지 않고, Off-line 알고리즘이다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int sorted[10];

void merge(int init[], int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = left;


	while (i <= mid && j <= right) {
		if (init[i] <= init[j])
			sorted[k++] = init[i++];
		else
			sorted[k++] = init[j++];
	}

	if (i > mid){
		for (int t = j; t <= right; t++)
			sorted[k++] = init[t];
	}
	else {
		for (int t = i; t <= mid; t++)
			sorted[k++] = init[t];
	}

	for (int t = left; t <= right; t++)
		init[t] = sorted[t];
}

void mergeSort(int a[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;

		mergeSort(a, left, mid);
		mergeSort(a, mid + 1, right);
		merge(a, left, mid, right);
	}
}

int main() {
	int arry[10] = { 10, 4, 6, 3, 2, 7, 1, 9, 8, 5 };

	mergeSort(arry, 0, 9);

	for (int i = 0; i < 10; i++)
		cout << arry[i] << ' ';

	return 0;
}

재귀를 이용해 나누고

비교해주면서 합치면 된다.

 

 

 

5. 퀵 정렬(Insertion Sort)

Time Complexity
- Best O(n log n)
- Avg O(n log n)
- Worst O(n²)
In-Place Algorithm
Off-line Algorithm
Unstable Sort

이름에서부터 알 수 있듯이, 평균적인 성능이 가장 좋다.

피벗(pivot)을 정하고, 피벗을 기준으로 피벗보다 작은 원소를 왼쪽, 큰 원소를 오른쪽으로 옮겨가며 분할 정복 방법으로 정렬을 진행한다.

 

참고로 C++ STL 에 있는 sort() 는 quick sort로 내부 구현이 되어 있다고 한다. (VS 6.0 기준)

 

#include <iostream>
#include <algorithm>
using namespace std;

void quickSort(int arry[], int start, int end) {
	if (start >= end)
		return;

	int key = start;
	int i = start + 1;
	int j = end;

	while (i <= j) {
		while (arry[i] <= arry[key])	//key 값보다 큰 값 만날 때까지 i 이동
			i++;
		while (arry[j] >= arry[key] && j > start)	//key 값보다 작은 값 만날 때까지 j 이동
			j--;
		if (i > j)
			swap(arry[j], arry[key]);
		else
			swap(arry[i], arry[j]);
	}

	quickSort(arry, start, j - 1);
	quickSort(arry, j + 1, end);
}

int main() {
	int i, j, key;
	int arry[10] = { 10, 4, 6, 3, 2, 7, 1, 9, 8, 5 };

	quickSort(arry, 0, 9);

	for (i = 0; i < 10; i++)
		cout << arry[i] << ' ';
	return 0;
}