6. 정렬 (1) - 삽입 정렬, 버블 정렬, 퀵 정렬

 

삽입 정렬

모든 요소를 앞에서부터 차례대로 정렬된 부분과 비교하여 위치를 찾아 삽입하는 방법.

void InsertionSort(int[] data){//삽입정렬
	for (int i = 1; i < SIZE; i++) { 
		key = data[i]; //키 값.
		for (j = i-1; j >= 0; j--) { //앞에 정렬되어 있는 부분에서 해당하는 위치를 찾아 삽입
			if (data[j] > key) {
				data[j + 1] = data[j]; //한칸 옆으로 이동
			}
			else {
				break;
			}
		}
		data[j + 1] = key; 
	}
}

시간복잡도

• BestCase : 이미 정렬된 경우 -> 이동 없이 각각 1번의 비교씩 $O(N)$
• WorstCase : 입력 자료가 역순인 경우 등 (마지막이 4 3 1 2 으로 된 경우) ->$\sum_{i=1}^{n-1}i = \frac{n(n-1)}{2}$ -> $O(N^2)$ + 이동횟수 (배열인 경우 모두 한 칸씩 밀어내야함)
• AverageCase : $O(N^2)$

AverageCase 증명

Q : 삽입정렬에서 원소를 정렬된 배열에 삽입할 때, 이진 탐색을 사용하면 $lgN$만 시간이 소요되므로 시간 복잡도가 줄지 않을까?
A : 어차피 자료구조가 배열이라 삽입할때 옆으로 한 칸씩 밀어야함 (결국 모든 원소를 방문하긴 해야됨)
Q : 삽입을 편하게 할 수 있는 연결리스트를 사용하면?
A : 연결리스트는 임의의 원소에 접근하지 못하기 때문에 이진탐색을 할 수 없음.

 

버블 정렬

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

void BubbleSort(int data[], int n){
  int temp;
  for(int i = SIZE-1; i > 0; i--){
      for(int j = 0; j < i; j++){
          if(data[j] < data[j + 1]){
              temp = data[j];
              data[j] = data[j + 1];
              data[j + 1] = temp;
      }
    }
  }
}

시간복잡도

Best, Worst, Average 모두 일정하게 검사 -> $\sum_{i=1}^{n-1}i = \frac{n(n-1)}{2}$ -> $O(N^2)$ (여기서 역순인 경우 교환횟수 3번 포함.)

 

퀵 정렬

앤서니 리처드 호어가 개발한 정렬 알고리즘.
분할 정복(Divide and conquer) 방법으로 문제를 작은 문제로 분할 후 해결, 이후에 결과를 모아 원래의 문제를 해결하는 방식.
재귀 호출 or 큐를 사용해서 구현가능.
피봇을 고른 후, 피봇보다 작은 요소들은 왼쪽으로 피봇보다 큰 요소들은 오른쪽으로 옮김. (이 과정에서 무조건 pivot은 제자리를 찾음)
이 오른쪽과 왼쪽 리스트를 각각 또 퀵소트로 정렬. -> 리스트의 크기가 0이나 1이 될 때까지 반복.

void quickSort(int data[],int max) {	//큐를 사용하여 구현
	int left, right;
	int lower_point, upper_point;
	int key, temp;

	left = 0;
	right = max-1;

	push(right);
	push(left);

	while (top >= 0) {
		left = pop();
		right = pop();

		//랜덤으로 키값 설정
		if (right - left > 0) {
			temp = rand()%(right-left+1) + left;
			key = data[temp];
			data[temp] = data[right];
			data[right] = key;

			lower_point = left - 1;
			upper_point = right;

			while (1) {	//왼 ---> / <----오
				while (data[++lower_point] < key);
				while (data[--upper_point] > key);

				if (lower_point >= upper_point) break;	//겹침

				temp = data[lower_point];
				data[lower_point] = data[upper_point];
				data[upper_point] = temp;
			}
			//data[right] == key 즉 한번 분할 끝날때마다 key값은 자기 위치로 가는것.
			temp = data[lower_point];
			data[lower_point] = data[right];
			data[right] = temp;

			push(right);	//오른쪽 ~ 피봇 +1
			push(lower_point + 1);
			push(lower_point - 1);	//피봇-1 ~ 맨 왼쪽
			push(left);
		}
	}
}

void push(int val) {
	if (top >= SIZE - 1) {
		return;
	}
	else {
		stack[++top] = val;
	}
}
int pop() {
	if (top < 0) {
		return;
	}
	else {
		return stack[top--];
	}
}

시간복잡도

• BestCase : 정확히 리스트가 반씩 나뉘는 경우 -> n번 비교를 $lgn$번 $O(NlgN)$
• WorstCase : Pivot이 계속 불균형하게 잡히는 경우 (이미 정렬된 리스트에서 피봇을 맨 앞or 뒤에서 잡을 때) $\sum_{i=2}^{n}(i-1) = \frac{n(n-1)}{2}$ -> $O(N^2)$
• AverageCase : $O(NlgN)$

AverageCase 증명

 

이후에 나올 합병(머지) 정렬, 힙 정렬보다 같은 시간복잡도이지만 퀵 정렬이 실제로 더 빠르다. 매번 퀵 소트 실행마다 피벗 1개는 무조건 정렬되어 제외되는 특성과 불필요한 데이터의 이동이 적기 때문이다.