정렬(선택,버블,삽입,병합,퀵,힙) / 무엇이 가장 빠르고 왜 빠른가 (동작과정)

(2) [게임코딩급행열차] 정렬 알고리즘 - YouTube

1.선택정렬

정렬되지 않은 데이터들 중에서 가장 작은 값을 추출하여 가장 맨 앞으로 정렬해나가는 알고리즘

시간복잡도

매 실행마다 최솟값 찾아야 하므로 이중 for문 사용하여 O(n^2)

 

2.버블정렬

인접한 두 수를 계속해서 비교하는 정렬 알고리즘

맨 뒤 인덱스부터 앞으로 정렬이 될 것임

시간복잡도 : O(n^2) 

매번 자리를 바꿔야 하므로 비효율적임 (데이터가 많아졌을 경우 엄청난 연산)

 

3.삽입정렬

자료 배열의 모든 요소를 앞에서 부터 비교하고자 하는 타겟값(tmp)과 정렬된 값을 비교하여 자신의 위치를 찾아 삽입하면서 정렬해나가는 알고리즘이다.

매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교하여 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣는다. 

시간복잡도

최선일 경우: 거의 다 정렬이 되어있을 경우 O(n) (tmp 바로 앞에서부터 맨앞으로 역순으로 참조하기 시작하는데 바로 앞과 비교했을 때 끝났을 경우 바로 break하기 때문)

최악일 경우: n(n-1)/2번 비교 = O(n^2)

각 인덱스마다 멈춰서서 역으로 비교해나가면서 tmp가 더 작아질때마다 swap

 

4.병합정렬

정렬할 데이터들을 쪼갤 수 없을 때까지 반으로 쪼개고 각각 정렬한 후 나중에 합치는 알고리즘

시간복잡도: 어떤 상황에서도 O(N * logN)

#include<iostream>

using namespace std;

int N,arr[1000001];
int *arr2;

void merge(int left, int right)
{
	int mid = (left + right) / 2;

	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i] <= arr[j]) 
			arr2[k++] = arr[i++]; 
		else
			arr2[k++] = arr[j++];
	}

	int tmp = i>mid ? j : i;
	
	while(k<=right) arr2[k++] = arr[tmp++];

	for (int i=left;i<=right;i++) arr[i] = arr2[i];
}

void partition(int left,int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2; 
		partition(left, mid);
		partition(mid + 1, right);
		merge(left, right);
	}
}

int main()
{
	scanf("%d",&N);
	arr2 = new int[N];
	for (int i=0;i<N;i++) scanf("%d",&arr[i]);

	partition(0, N - 1);

	for (int i=0;i<N;i++) printf("%d\n",arr[i]) ;
}

새로운 *arr라는 포인터배열이 필요함

매번 정렬된 데이터를 담을 배열 공간이 추가적으로 필요하다는 점에서 메모리 사용이 비효율적

 

5.퀵정렬

어떤 키값을 기준으로 작은값, 큰값을 나누는 방법

시간복잡도

평균: O(NlogN)

최악의 경우 : O(N^2) (거의 정렬되어있을 때는 분할 정복 알고리즘이 안되므로 삽입정렬과 반대로 최악이 됨)

#include <iostream>
using namespace std;
//퀵정렬
int n,cnt, quick[10000001];

void quickSort(int i, int j)
{
	if(i>=j) return;
	int pivot = quick[(i+j)/2];
	int left = i;
	int right = j;
	
	while(left<=right)
	{
		while(quick[left]<pivot) left++;
		while(quick[right]>pivot) right--;
		if(left<=right)
		{
			swap(quick[left],quick[right]);
			left++; right--;
		}
	}
	quickSort(i,right);
	quickSort(left,j);
}

int main() 
{
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		scanf("%d",&quick[i]);

	quickSort(0,n-1);

	for(int j = 0; j < n; j++) // 출력
		printf("%d\n",quick[j]);
}

 

6.힙정렬

완전 이진트리를 생성하는 알고리즘

병합 정렬과는 다르게 추가적인 메모리가 필요하지 않고, 항상 NlogN의 정렬 성능을 보여주기 때문에 퀵정렬보다 안정적

힙 생성 O(logN) * 힙 정렬 O(n) => O(nlogN)