Quick sort 특징
시간 복잡도에 따라서 o(nlogn)의 빠른 속도이지만, 데이터 값에 따라 O(n^2)나올 수 있다.
특정 범위에서 (start ~ end) 가장 왼쪽에 있는 숫자를 pivot으로 배치한다.
여러번의 swap 작업을 통해 pivot 의 위치를 결정하고, \
pivot 왼쪽에는 pivot보다 작은숫자를
pivot 오른쪽에는 pivot 보다 큰 숫자를 배치한다.
이 작업이 한번 끝나면 pivot의 4의 위치가 결정된다.
이번에는 구간을 나누어서 같은 작업을 진행하면 된다.
가장 작은 구간이 될때까지 재귀호출을 통해서 반복하여 위작업을 실행해준다.
세부과정
start = 0/ end 7 일때 가장 왼쪽을 pivot으로 둔다.
변수 a를 start + 1, 변수 b를 end로 설정해준다.
a++ 하면서 pivot보다 큰숫자를 찾는다.
b— 하면서 pivot보다 작은숫자를 찾는다.
찾았으면 swap하여 바꿔주고, 이과정을 a와 b가 엇갈리기 전까지 반복해준다.
엇갈렸으면 마무리 단계로 pivot과 b를 swap하면 된다.
이제 pivot왼쪽에는 전부 pivot보다 작은숫자들이 배되고, 오른쪽에는 큰 숫자들이 배치되게 된다.
0~7번 구간 까지 이 과정을 끝냈고, 이제 재귀호출을 통해 pivot 왼쪽 구간 (0~2), pivot 오른쪽 구간(4~7)에 대해서 이 과정을 또 수행시켜주면 된다.
#include <iostream>
int vect[10] = { 4,3,9,8,5,7,1,2 };
int n = 8;
void quicksort(int start, int end)
{
if (start >= end)
return;
int pivot = start;
int a = start + 1;
int b = end;
while (true)
{
while (a <= end && vect[a] <= vect[pivot])
a++;
while (b >= start && vect[b] > vect[pivot])
b--;
if (a > b)
break;
std::swap(vect[a], vect[b]);
}
std::swap(vect[pivot], vect[b]);
quicksort(start, b - 1);
quicksort(b + 1, end);
}
char main()
{
quicksort(0, n - 1);
return 0;
}
Python
복사
#include <iostream>
int vect[10] = { 4,3,9,8,5,7,1,2 };
int n = 8;
void quicksort(int left, int right)
{
int i = left, j = right;
int pivot = vect[(left + right) / 2];
/* partition */
while (i <= j)
{
while (vect[i] < pivot)
i++;
while (vect[j] > pivot)
j--;
if (i <= j)
std::swap(vect[i++], vect[j--]);
};
/* recursion */
if (left < j)
quicksort(left, j);
if (i < right)
quicksort(i, right);
}
char main()
{
quicksort(0, n - 1);
return 0;
}
Python
복사
“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”
혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.
•
강의는 다 들었지만 막상 손이 안 움직이고,
•
복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고,
•
질문할 곳도 없고,
•
유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고.
문제는 ‘연습’이 빠졌기 때문입니다.
단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.
실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.
그래서, 얌얌코딩 코칭은 다릅니다.
그냥 가르치지 않습니다.
스스로 설계하고, 코딩할 수 있게 만듭니다.
얌얌코딩 코칭에서는 단순한 예제가 아닌,
스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.
이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:
•
문제를 스스로 쪼개고 설계하는 힘
•
다양한 조건을 만족시키는 실제 구현 능력
•
기능 단위가 아닌, 프로그램 단위로 사고하는 습관
•
마침내 자신의 힘으로 코드를 끝까지 작성하는 경험
지금 필요한 건 더 많은 강의가 아닙니다.
코드를 스스로 완성해 나가는 훈련,
그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.
자세한 안내 보기: 프리미엄 코칭 안내 바로가기 또는 카카오톡 상담방: 얌얌코딩 상담방