이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌7 - Algorithm - 일 년 전 등록

퀵 정렬(quick sort)

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

안녕하세요. 이번 시간에는 퀵 정렬에 대해 알아보겠습니다.

이름처럼 빠릅니다. 정확히는 재수가 없지 않으면 빠릅니다. 재수가 없으면 매우 느립니다. 하지만 재수없는 경우가 희박하기 때문에 많이 사용됩니다. 빠르기로 유명한 합병 정렬보다 평균 두 배 빠릅니다. 관심이 생기죠? 대신 합병 정렬보다 코드가 어려우니 차분히 보셔야할 겁니다. 

단점도 있는데 운이 나쁘면 느리다는 것(극복하는 방법이 있습니다)입니다. 또 다른 단점으로 같은 숫자들을 정렬할 경우 순서가 섞일 수 있다는 겁니다. 예를 들면 100이 3개가 있고 각각 1번, 2번, 3번 번호가 매겨져 있을 때 퀵 정렬 방법으로 정렬하면 1,2,3번 순서가 아닌 다른 순서로 정렬될 수도 이있습니다. 같은 100인데 그 순서가 뭐가 중요하냐고 할 수도 있지만, 실제 데이터에서 100이 금액이고, 1번 2번 3번이 사람의 순서라면 금액 순으로 정렬을 했을 때 사람의 순서가 달라지는 불상사가 생기는 겁니다. 이 점들을 고려하여 퀵 정렬을 사용하셔야 합니다. 

합병 정렬처럼 분할 정복 기법을 사용합니다. 그 상태로 문제를 해결하지 못할 때 작게 쪼개어 해결하는 거죠.

[4,1,7,6,5,8,2,3] 어떠한 한 숫자를 고릅니다. 기준으로 5를 골랐습니다. 5를 가장 오른쪽으로 보냅니다.
[4,1,7,6,3,8,2,5] 이제 왼쪽에는 기준보다 작은 수가, 오른쪽에는 기준보다 큰 수가 나오도록 조정하여 보겠습니다.
[4,1,7,6,3,8,2,5] 5를 제외한 가장 왼쪽과 오른쪽 수를 조작합니다. 이제부터 규칙은 다음과 같습니다. 집중해서 읽어주세요. 왼쪽 수는 기준보다 작으면 다음으로 넘어가고, 크면 가만히 있습니다. 오른쪽 수는 기준보다 크면 다음으로 넘어가고, 작으면 가만히 있습니다. 이렇게 넘어가다가 왼쪽은 기준보다 크고, 오른쪽은 기준보다 작으면 서로 바꿔줍니다.
[4,1,7,6,3,8,2,5] 왼쪽 4는 기준보다 작기 때문에 다음 수로 넘어가고, 오른쪽 2은 기준보다 작기 때문에 가만히 있습니다.
[4,1,7,6,3,8,2,5] 왼쪽 1도 다음 수로 넘어가고, 오른쪽 2는 계속 가만히 있습니다.
[4,1,7,6,3,8,2,5] 왼쪽 7는 기준보다 크고, 오른쪽 2은 기준보다 작기 때문에 서로 바꿔줍니다.
[4,1,2,6,3,8,7,5] 왼쪽 6은 기준보다 크기 때문에 가만히 있고, 오른쪽 8은 기준보다 크기 때문에 다음 수로 넘어갑니다.
[4,1,2,6,3,8,7,5] 왼쪽 6은 기준보다 크고, 오른쪽 3은 기준보다 작기 때문에 서로 바꿔줍니다.
[4,1,2,3,6,8,7,5] 이제 더 이상 비교할 수가 없네요. 왼쪽과 오른쪽 수가 만났습니다.
[4,1,2,3,6,8,7,5] 그러면 만난 수인 6과 기준인 5를 바꿔줍니다.
[4,1,2,3,5,8,7,6] 이제 5를 기준으로 왼쪽에는 5보다 작은 수가, 오른쪽에는 5보다 큰 수들만 남았습니다. 신기하죠?
아직 정렬이 완료되지 않았기 때문에 끝이 아닙니다. 이제 5를 기준으로 왼쪽([4,1,2,3]), 오른쪽 배열([8,7,6])로 나누어 재귀적으로 퀵 정렬을 해줍니다. 이렇게 계속 하면 정렬이 완료됩니다.

코드로 볼까요? 코드를 간단하게 하기 위해 정렬하는 부분과 재귀하는 부분을 나누어주었습니다.

var partition = function(array, left, right, pivotIndex) { // 정렬하는 부분
  var temp;
  var pivot = array[pivotIndex];
  while (left <= right) { // 왼쪽, 오른쪽 수를 규칙과 비교해 다음 수로 넘어갑니다.
    while (array[left] < pivot)
      left++;
    while (array[right] > pivot)
      right--;
    if (left <= right) { // 왼쪽이 기준보다 크고, 오른쪽이 기준보다 작으면
      temp = array[left];
      array[left] = array[right];
      array[right] = temp; // 서로 바꿔줍니다.
      left++;
      right--;
    }
  }
  temp = array[left];
  array[left] = array[pivotIndex];
  array[pivotIndex] = temp; // 마지막으로 기준과 만난 수를 바꿔줍니다. 기준의 위치는 이제 i입니다.
  return left;
};

var quickSort = function(array, left, right) { // 재귀하는 부분
  if (!left) left = 0;
  if (!right) right = array.length - 1;
  var pivotIndex = right; // 배열 가장 오른쪽의 수를 기준으로 뽑습니다.
  pivotIndex = partition(array, left, right - 1, pivotIndex); // right - 1을 하는 이유는 기준(현재 right)을 제외하고 정렬하기 위함입니다.
  if (left < pivotIndex - 1)
    quickSort(array, left, pivotIndex - 1); // 기준 왼쪽 부분 재귀
  if (pivotIndex + 1 < right)
    quickSort(array, pivotIndex + 1, right); // 기준 오른쪽 부분 재귀
  return array;
};

quickSort([4,1,7,6,3,8,2,5]); // [1,2,3,4,5,6,7,8]

성능은 최악의 경우 O(N^2)이고  최악의 경우를 제외하면  O(NlogN) 정도 됩니다. O(N^2)이 나오는 경우는 매우 희박하기 때문에 보통 O(NlogN)으로 취급합니다. 같은 NlogN이지만 합병 정렬보다는 두 배 빠르기 때문에 더 자주 쓰입니다.

최악의 경우는 기준(pivot)으로 뽑은 수가 항상 제일 큰 수이거나 제일 작은 수일 경우입니다. 이럴 경우는 나중에 두 배열로 나누더라도 한 배열은 비어있고, 한 배열은 꽉 차있습니다. 하지만 이렇게 운이 나쁜 경우는 거의 없겠죠?

퀵 정렬은 (물론 조금 변형되었지만) 대부분의 프로그래밍 언어에서 배열.sort()할 때 내부적으로 사용됩니다. 물론 합병 정렬도 간혹가다 사용되지만요. 다음 시간에는 계수 정렬에 대해 알아보겠습니다!

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

2개의 댓글이 있습니다.
일 년 전
답변감사합니다. 한가지더..질문이 좀 장황한데요.. quickSort의 재귀호출은 pivotIndex가 1이하가 될때까지 28번재 라인의 if문을 계속타다가 1이하가 되면 30번째 라인의 if문을 타게 되면서 left의 값이 변함에 따라 이후는 계속 30번째 라인의 if문을 타면서 pivotIndex의 값이 변화하게되고 어느순간 정렬이 다 되면 이제 pivotIndex의 값은 6이나 7을 반환하게 됨으로써 30번째 라인의 if문조건도 만족하지 않게되고 배열을 리턴하는 거같은데요. 리턴하게 되면 이전의 재귀함수는 더 진행할 코드가 있더라도 더이상 실행되어지지 않게 되는건지 궁금합니다.
일 년 전
아뇨 처음부터 끝까지 조건만 만족한다면 계속 28번째와 30번째 if 문이 둘 다 실행됩니다. 둘 중 하나만 실행되는 게 아닙니다. 또한 재귀함수는 특성상 모든 내부적으로 작동하는 재귀함수가 종료되어야 전체가 종료됩니다. 코드를 다시 분석해보세요.
일 년 전
안녕하세요. 코드 9번째 줄의 if문에 left <= right 로 되어있는데 left == right 가 되는 경우가 존재하는지 궁금합니다.
일 년 전
네 생깁니다. 위의 코드에서는 left, right가 각각 0, 0 그리고 6, 6인 경우가 생기네요.