[C/C++] 정렬

1. 선택정렬

(1) 선택정렬이란 : 전체의 데이터를 한번씩 확인하며 그 데이터를 적절한 위치로 이동시키는 것을 의미한다.
(2) 오름차순으로 정렬하는 경우 : N개의 데이터가 입력될 때 n번째로 작은 데이터를 n번째 위치로 옮기는 과정을 정렬이 완료될 때까지 반복한다. 한 데이터를 옮길 때마다 나머지 N-n-1개의 데이터와 비교하게 된다.
(3) 시간복잡도 : N개의 데이터에 대해 실행되는데 그 연산 횟수가 N+(N-1)+(N-2)+...+2이므로 N(N+1)=N²+N이다. 따라서 시간복잡도는 O(N²)이다.

#include<iostream>
using namespace std;

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

	for (int i = 0; i < 10; i++) {
		for (int j = i; j < 10; j++) {
			if (arr[j] < arr[i]) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}

	for (int i = 0; i < 10; i++)
		cout << arr[i] << " ";
	cout << endl;
}

 

2. 삽입정렬

(1) 삽입정렬이란 : 특정한 데이터를 적절한 위치에 삽입하는 것을 의미한다.
(2) 오름차순으로 정렬하는 경우 : 맨 앞의 데이터는 그 자체로 정렬된 것으로 생각하여 두 번째 데이터부터 정렬을 시작한다. 두 번째 데이터가 첫 번째 데이터보다 작을 경우 맨 앞으로 이동한다. 세 번째 데이터가 첫 번째나 두 번째에 위치한 데이터보다 작을 경우 맨 앞으로 이동한다. 이 과정을 모든 데이터에 대해 실행한다.
(3) 시간 복잡도 : 모든 데이터가 거의 정렬된 상태라면 최선의 경우로 O(N)이지만, 최악의 경우 O(N²)이다.

#include<iostream>
using namespace std;

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

	for (int i = 0; i < 9; i++) {
		for (int j = i + 1; j > 0; j--) {
			if (arr[j - 1] > arr[j]) {
				int temp = arr[j - 1];
				arr[j - 1] = arr[j];
				arr[j] = temp;
			}
		}
	}

	for (int i = 0; i < 10; i++)
		cout << arr[i] << " ";
	cout << endl;
}

 

3. 퀵정렬

(1) 퀵정렬이란 : 집합에서 기준이 되는 데이터를 정한 후 그 데이터보다 큰 값과 작은 값의 데이터 위치를 서로 바꾸는 것이다. 기준이 되는 데이터(pivot)는 주로 맨 앞에 위치한 데이터이며, 비교하는 두 데이터는 pivot의 다음에 위치한 데이터와 맨 뒤의 데이터이다.
(2) 오름차순으로 정렬하는 경우 : pivot=0, lptr=1, rptr=배열길이-1로 설정한 후 배열[lptr]과 배열[rptr]을 서로 비교한다. 배열[lptr]이 pivot보다 크고 배열[rptr]이 pivot보다 작으면 배열[lptr]과 배열[rptr]의 자리를 서로 바꾼다. 그리고 lptr의 값을 증가시키고 rptr의 값을 감소시킨다. 만약 배열[lptr]의 값이 pivot보다 작거나, 배열[rptr]의 값이 pivot보다 크다면 값을 바꾸지 않고 lptr, rptr의 값만 변경한다. lptr과 rptr의 값이 같아지면 pivot의 값을 배열[lptr]로 옮긴다. pivot의 값을 기준으로 왼쪽에는 pivot보다 작은 값들이 있고 오른쪽에는 더 큰 값이 있다. 따라서 pivot의 왼편과 오른편에 대해 위의 과정을 다시 반복하면 된다.
(3) 시간복잡도 : O(NlogN)

#include<iostream>
using namespace std;

void Quick_sort(int arr[], int start, int end) {
	if (start >= end)
		return;

	int pivot = start, lptr = start + 1, rptr = end;

	while (lptr <= rptr) {
		if (arr[lptr] > arr[pivot] && arr[rptr] < arr[pivot]) {
			int temp = arr[lptr];
			arr[lptr] = arr[rptr];
			arr[rptr] = temp;
			lptr++;
			rptr--;
		}
		else if (arr[lptr] <= arr[pivot])
			lptr++;
		else if (arr[rptr] >= arr[pivot])
			rptr--;
		else {
			lptr++;
			rptr--;
		}
	}

	int temp = arr[pivot];
	arr[pivot] = arr[rptr];
	arr[rptr] = temp;

	Quick_sort(arr, start, rptr - 1);
	Quick_sort(arr, rptr + 1, end);
}


int main() {
	int arr[10] = { 7,5,2,4,1,3,6,9,0,8 };
	int start = 0, end = 9;
    
	Quick_sort(arr, start, end);

	for (int i = 0; i < 10; i++)
		cout << arr[i] << " ";
	cout << endl;
}

 

4. 계수정렬

(1) 계수정렬이란 : 집합 내에서 데이터의 위치를 직접 이동시키지 않고 또다른 집합을 생성해 그 인덱스를 활용해 값을 반환하는 방법이다.
(2) 오름차순으로 정렬하는 경우 : 정렬하고자 하는 집합의 최솟값과 최댓값이 모두 담기도록 배열을 생성한다.(최댓값이 20이라면, 새로 생성할 배열의 크기는 21이어야 한다.) 배열 원소의 초기값은 모두 0이다. 집합의 데이터를 순서대로 하나씩 읽으면서 집합의 데이터 값과 배열의 인덱스 값이 같다면 그 인덱스에 해당하는 배열 원소 값을  하나씩 증가시킨다. 모든 원소를 다 읽었다면 배열의 인덱스값을 그 배열 원소에 저장된 값 만큼 출력한다.(원래 집합에 5가 두 번 등장했다면, 배열의 인덱스가 5인 원소의 값은 2 이므로 5가 두 번 출력된다.)
(3) 시간복잡도 : O(N+M) (M은 최댓값)

#include<iostream>
using namespace std;

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

	int arr2[10] = { 0 };
	for (int i = 0; i < 10; i++) 
		arr2[arr[i]]++;
	

	for (int i = 0; i < 10; i++) 
    	if (arr[i]!=0)
        	for (int j = 0; j < arr2[i]; j++) 
				cout << i << " ";
	
	cout << endl;
}