야매 개발자 알고리즘 퀵 정렬[Quick Sort]

얼마전 쿠팡에서 서류 합격 메일이 날아왔다. 구글링을 해보니 쿠팡같은 경우 서류는 거의다 통과시켜 놓고 

problem solving test를 통해서 엄청나게 걸러버리는 듯 하다.

개발자로 취직해서 일한지 2년이 가까워 지면서 웹쪽 HTML CSS JS는 많이 해봤지만

순수 자바 쪽은 거의 건들이지 않았다는 것에서 불안감이 엄청나게 느껴졌다.

학교에서 전공수업 잘 듣고 자료구조나 알고리즘 공부 열심히 했으면 붙을 수 있다고 하는데

난 전공자가 아니다;; 학교에서 기초적인걸 배우긴 했지만 자바 클래스 만들고 'Hello word' 띄우는 수준?

안드로이드로 인텐트 날려서 화면 전환하는 정도 까지만 배웠고 이론적인건 소프트웨어공학 원론쯤?

그 외엔 죄다 마케팅이나 경영, 혹은 발표과제로 점수먹는 수업이라든지 실음과 전공수업이나 들었지 ㅋ

말하자면 전공이라기 보단 반공(?)이라고 말하는게 어울릴 듯 하다.

아무튼 자료구조는 스택과 큐밖에 모르고 정렬 알고리즘은 버블정렬 밖에 모르는 상태에서

어렵다고 소문난 쿠팡 테스트를 통과하려면 짧은 시간동안 공부를 많이 해야 겠다 싶었다.

면접 후기라던지 자료구조 기초라던지 알고리즘을 어떻게 공부해야 하는지 찾아 보면서

퀵정렬이라는 것이 있다는걸 태어나서 어제 처음 알게 되었다.

버블정렬만 있으면 만사 오케이인줄 알았고 심지어 프로젝트중에선 DB에서 불러올때 ORDER BY만 떄려버리면 해결이니

정렬 알고리즘을 사용할 필요성도 못느끼고 있었는데....  좀 충격이었다.

심지어 아래 동영상을 보고 가장 먼저 들었던 생각은

"버블정렬 개쓰레기였네??"

일단 정렬의 종류는 여러가지 있는데 아래 영상을 보도록 하자. 가운데 표시된 퀵정렬이 대체로 가장 빠른 결과를 보여준다. <출처: Viktor Bohush, 유튜브>

그리고 퀵정렬에 대해서 좀더 큰화면으로 보자면 <출처: Timo Bingmann / 유튜브>

이렇게 보여질 수 있다.

해당 내용을 직접 포스팅 하려 해보았으나 알고리즘이나 기초지식이 1도 없는 상태에서 이해 할 수 있는 포스팅 만드는데

시간이 너무 오래 걸린다. 퀵정렬이 무엇인지 이곳 저곳 둘러보던중

아주아주아주 설명을 잘 해놓은 게시글을 발견했다.

허접하게 내가 만드는 것 보다는 정말 잘 만든 다른사람의 글을 보는 것이 더 나을 것이라고 판단 했다.

http://navercast.naver.com/contents.nhn?rid=2871&contents_id=90163

위 주소로 들어가보면 퀵정렬에 대해 아주 잘 설명해 놓은 글이 있다.

한번 쭉 읽어 보고 이해가 좀 되겠다 싶다면 슈도코드 부분은 스킵하고 다음 소스를 보도록 하자

// 값을 비교하고 로우와 하이를 이동시키면서 값의 교환이 이루어지는 함수
public static int partition(int arr[], int left, int right) {
 
    int pivot = arr[(left + right) / 2];
 
    while (left < right) {
        while ((arr[left] < pivot) && (left < right))
            left++;
        while ((arr[right] > pivot) && (left < right))
            right--;
 
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
 
    return left;
}
 
 
public static void quickSort(int arr[], int left, int right) {
 
    if (left < right) {
        // 값을 비교하고 로우와 하이를 이동시키면서 값의 교환이 이루어지는 함수
        int pivotNewIndex = partition(arr, left, right);
        // quick sort의 설명중
        // 자주 나오는 '재귀', '분할' 이라고 설명되어지는 부분이다.
        quickSort(arr, left, pivotNewIndex - 1);
        quickSort(arr, pivotNewIndex + 1, right);
    }
 
}
 
// 
public static void main(String[] args) {
    int[] arrs = { 69, 10, 30, 2, 16, 8, 31, 22 };
    quickSort(arrs, 0, arrs.length - 1);
    System.out.println("결과");
 
    for (int i : arrs) {
        System.out.print(i + " ");
    }
}

<참조: http://creatordev.tistory.com/70>

처음 올린 링크의 글을 정독했다면 위 소스를 보면서 직접 소스를 디코딩 해보도록 하자.

소스의 처음부터 정렬이 종료될때까지 직접 소스를 따라가면서 정렬을 해보는 것이 이해하는데 가장 큰

도움이 될 것이다.

요즘 웹쪽엔 내가 아는 지식이 후달려서 더 포스팅하기 힘들었는데 노드js나 리엑트js 해보기 전까진

자료구조와 정렬에 대해서 포스팅을 해봐야 겠다. 나에게도 큰 도움이 되는듯 하다.