합병 정렬 (Merge Sort)와 같이, 퀵 정렬도 분할 정복 메서드를 이용하는 정렬 알고리즘이다. 다른 분할 정복 알고리즘과 같이 정렬되지 않은 한 배열을 둘로 나누다. 바로 배열을 나누기 위해 파티션 (partition)알고리즘을 추가로 구현했다. 합병 정렬과 다르게, 퀵 정렬은 가운데 지점 (midpoint)에서 배열을 나누지 않는다. 배열은 나눌때 한 배열은 지점 (pivot)보다 작은 정수들이 들어있고 나머지 한 배열은 지점보다 큰 정수들이 들어있다. 반복적으로 지점이 바뀌어지면서 배열은 반복적으로 나누어진다 각 배열에 1개의 정수가 남을 때 까지. 이제, 합병 정렬과 마찬가지로, 모든 배열들을 다시 한 배열로 합치면서 동시에 정렬 시킨다. 이해하기 쉽게 비주얼을 추가했다. 메서드: 분할 정복..

이번 글에서는 정렬 알고리즘들 중에 가장 기초적인 거품 정렬에 대해 살펴보겠다. 만약 알고리즘 스터디, 혹은 컴퓨터 공학 과정에서 자료구조 중에 정렬 알고리즘들을 배웠다면, 아마 거품 정렬을 제일 먼저 접해봤을 것이다. 간략하게 설명하자면, 배열 A에서 위치 x가 주어졌다. 그럼 A[x] > A[x + 1]을 비교하게 된다. 만약 진짜 A[x] > A[x + 1]이 맞으면, A[x]값과 A[x + 1] 값이 서로 교체 (swap)한다. 그리고 비교 지점이 한 칸씩 앞으로 이동한다. 만약 마지막 위치가 n이고 배열 A[n - 1]과 A[n] 비교가 마치면, 다시 첫번째 배열 위치 A[0]로 돌아가서 다시 A[1]을 비교하게 된다. 모든 배열들이 정렬했을 때 까지 이런식으로 반복된다. 만약 위에 있는 글이 ..

선택 정렬은 간략하게 설명하자면 끝에서 잡던, 앞에서 잡던, 한 지점을 잡고 시작하며 현재 찾은 제일 낮은 값을 맨 앞으로 옮긴다. 예를 들면 한 배열이 A가 다음 숫자들을 다음과 같이 정의했다: [5, 4, 7, 3]. A[0...3]에서 가장 적은 값이 3이며, 3이 맨 앞자리 A[0]에다 옮겨지며 기존에 있던 A[0]값 -> 5는 기존에 있던 3의 위치 -> A[3]에 옮겨진다. 이제 A[1...3]에서 가장 적은 값을 찾아야하는데 가장 적은 값은 A[1]에 위치한 4이다. 따라서 A[1]에 4가 유지되며 바꿔치기를 할 필요가 없다. 대충 A[3]까지 반복이 되면서 [3, 4, 5, 7]로 정렬된다. 이해가 안 갔으면 다음 비쥬얼을 참고하면 된다. 메서드: Naive 네이브 의사코드는 다음과 같다...

분할 정복 (Divide and Conquer) 메서드의 기초 알고리즘 중 하나다. Insertion Sort랑 같은 목표 (배열을 정렬하기)를 갖고 있지만 과정은 Insertion Sort보다 많다. 배열을 계속 반복적으로 둘로 분할한다 한 개씩 남을 때 까지. 정복하는 과정은 여기서 부터 시작된다. 먼저 방금전 까지 나누어진 배열 요소들 끼리 정렬한 다음에 반복적으로 Insertion Sort와 같은 방식으로 정렬 시켜서 왼쪽과 오른쪽 배열들을 만든다. 왼쪽 배열에 소속이 되있는 요소들과 오른쪽 배열에 소속이 되있는 요소들 끼리 비교하면서 정렬하고 합치면 정렬된 배열이 완전체가 된다. 위 설명을 못 알아들었으면 비주얼을 참고하자. 메서드: 분할 정복 (Divide and Conquer) 의사코드는 다..

이름과 다르게 추가 키 값을 삽입하지는 않는다. 그냥 입력한 배열에 있는 숫자들을 두 묶음으로 나뉘어 진다. 왼쪽 묶음은 정렬된, 오른쪽 묶음은 정렬 안 된. 정렬되지 않은 오른쪽 묶음에 있는 숫자들이 하나하나 왼쪽 묶음으로 옮겨지면서 각 정렬된 숫자들을 비교하며 적절한 자리를 잡는다. 물론 처음에 배열 전체가 정렬되지 않았을 초기 때는 둘 째 숫자 array[1] 가 첫 째 숫자 array[0]이랑 서로 비교를 시작하고 나서야 정렬된 왼쪽 묶음이 탄생한다. 말 그대로 array[n]이 array[n - 1]을 계속 비교한다. 내가 방금한 설명을 이해 못 했다면 비쥬얼로 설명하자. 메서드: 네이브 (Naive) 의사 코드는 다음과 같다. Insertion-Sort(A) for j = 1 to A.leng..