[Algorithm] Quick Sort(퀵 정렬)

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5#curriculum

[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의

 

위 강의의 5, 6강 퀵 정렬에 대한 리뷰이다.

 

 

 

재귀 함수를 이용해서 그런가 돌아가는 원리가 마치 플라나리아 재생실험 보는 느낌이었다.

 

쪼개지면서 정렬의 반복

 

 

#include <stdio.h>

int number = 10;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
//int array[10] = {3, 7, 8, 1, 5, 9, 6, 10, 2, 4}

void show() {
	int i;
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
}

void quickSort(int *data, int start, int end) {
	if (start >= end) { // 원소가 1개인 경우 그대로 두기 
		return;
	}
	
	int key = start; // 키는 첫번째 원소 
	int i = start + 1;
	int j = end;
	int temp;
	
	while (i <= j) { // 엇갈릴 때까지 반복 
		while(data[i] <= data[key]) { // 내림차순은 while(data[i] >= data[key])
			i++; // 큰값 만날 때까지 우측 이동 
		}
		while(data[j] >= data[key] && j > start) { // 내림차순은 while(data[j] <= data[key] && j > start)
			j--; // 작은값 만날 때까지 좌측 이동 
		}
		if (i > j) {
			// 엇갈린 경우(순서가 잡힌 경우) 키값교체 
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		} else {
			// 그 외는 swap 
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}
	
	// 재귀를 이용하여 각각 정렬 (분할 정복!) 
	quickSort(data, start, j - 1);
	quickSort(data, j + 1, end);
}


int main(void) {
	quickSort(array, 0, number - 1); 
	show();
	return 0; 
}

 

 

처음에 강의만 들었을 때는 왜 퀵정렬의 시간복잡도가 일반적으로 N * logN 인지 이해가 안 갔다. 구글링하다가 아래 블로그를 보고 얼추 이해하게 되었다.

 

 

https://zeddios.tistory.com/35

정렬 알고리즘 - Quick Sort (평균- nlogn, 최악- n^2)

 

 

특히 이 설명이 너무나도 압권이었음

 

 

 

 

최악의 경우에 시간복잡도가 n^2 이 나오는데 그 경우는 정렬할 샘플이 오름차순 혹은 내림차순으로 이미 정렬이 되어 있는 경우다.

 

분할 없이 숫자를 모두 훑으며 (다시) 정렬하기 때문에 n^2 가 나오는 것 같다.

 

 

출처: https://kodakit.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%80%B5-%EC%A0%95%EB%A0%AC-quick-sort-%EC%89%BD%EA%B2%8C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

 

 

 

이해해보려고 위 gif만 계속 들여다 봤다.

 

 

 

 

 

C++ 소스를 Java로 바꾸면

 

public class Sort
{
    private static void quickSort(int[] data, int start, int end) {
        if (start >= end) {
            return;
        }
        int key = start;
        int i = start + 1;
        int j = end;
        int temp;
        
        while (i < j) {
            while (i < data.length && data[i] < data[key]) {
                // index 에러나서 i < data.length 추가함
                i++;
            }
            while (data[j] > data[key] && j > start) {
                j--;
            }
            if (i > j) {
                temp = data[j];
                data[j] = data[key];
                data[key] = temp;
            } else {
                temp = data[j];
                data[j] = data[i];
                data[i] = temp;
            }
        }
        quickSort(data, start, j - 1);
        quickSort(data, j + 1, end);
    }
    
    public static void main(String[] args) {
        int[] array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.printf("%d ", array[i]);
        }
    }
}

 

이렇게 된다.

 

 

javascript 로 바꾼다면

 

function quickSort(data, start, end) {
    if (start >= end)  return;
    let key = start;
    let i = start + 1;
    let j = end;
    let temp;

    while (i < j) {
        while (i < data.length && data[i] < data[key]) {
            i++;
        }
        while (data[j] > data[key] && j > start) {
            j--;
        }
        if (i > j) {
            temp = data[j];
            data[j] = data[key];
            data[key] = temp;
        } else {
            temp = data[j];
            data[j] = data[i];
            data[i] = temp;
        }
    }
    quickSort(data, start, j - 1);
    quickSort(data, j + 1, end);
}

function sort() {
    let array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];
    quickSort(array, 0, array.length - 1);
    console.log(array.join(", "));
}

sort();

 

이렇게 바꿀 수 있다.

 

 

 

아래 코드의 경우 중간값을 피벗값으로 정한 뒤 그 값을 기준으로 분할 정렬한다.

참고를 위해 들고와 봄

 

function quickSort (array, left = 0, right = array.length - 1) {
  if (left >= right) {
    return;
  }
  const mid = Math.floor((left + right) / 2);
  const pivot = array[mid];
  const partition = divide(array, left, right, pivot);
 
  quickSort(array, left, partition - 1);
  quickSort(array, partition, right);
 
  function divide (array, left, right, pivot) {
    console.log(`array: ${array}, left: ${array[left]}, pivot: ${pivot}, right: ${array[right]}`)
    while (left <= right) {
      while (array[left] < pivot) {
        left++;
      }
      while (array[right] > pivot) {
        right--;
      }
      if (left <= right) {
        let swap = array[left];
        array[left] = array[right];
        array[right] = swap;
        left++;
        right--;
      }
    }
    return left;
  }
 
  return array;
}

출처: https://im-developer.tistory.com/135 [Code Playground]