gaeggu's blog gaeggu's blog

퀵 정렬은 합병 정렬과 함께 대표적인 분할 정복 알고리즘 중 하나이다. 여기서 분할 정복 알고리즘이란 하나의 큰 문제를 여러 개의 작은 문제로 나누어 문제를 해결하는 알고리즘을 뜻한다. 퀵 정렬은 특정 값을 기준으로 작은 값과 큰 값을 나눈다. 이때의 기준값을 피벗(pivot)이라 한다. 예시를 통해 살펴보자. 예시 다음 숫자들을 오름차순으로 정렬하라. 1. 분할 오름차순으로 정렬하기 위해서는 피벗보다 작은 값은 피벗 왼쪽에 피벗보다 큰 값은 피벗의 오른쪽에 와야 한다. 그리고 이를 위해서 배열 양쪽에 포인터를 두고, 왼쪽 포인터는 피벗보다 큰 값이 나올 때까지 이동하고 오른쪽 포인터는 피벗보다 작은 값이 나올 때까지 왼쪽으로 이동하며 값을 교환한다. 아래 그림을 보면 왼쪽 포인터는 피벗보다 큰 값을 찾..

개념 삽입 정렬은 특정 원소의 앞에 있는 원소들이 이미 정렬되어 있다는 가정 하에 앞에 원소에서 적절한 위치에 특정 원소를 삽입하는 정렬 방식이다. 예제를 살펴보면서 삽입 정렬이 어떻게 수행되는지 살펴보자. 예제 다음 숫자들을 오름차순으로 정렬하라. 삽입정렬에서는 앞에 있는 원소들이 정렬되어 있는 것을 가정하기 때문에 자신보다 작은 수(오름차순 시 우선순위가 높은 원소)를 만나면 바로 그 뒤가 삽입되어야 할 위치이고, 그 전까지는 큰 수를 만나면 하나씩 자신보다 뒤로 밀어낸다고 생각하면 된다. 10 앞에는 삽입할 위치가 없으니 3부터 시작해보자. 3 앞에 있는 원소들이 정렬되어 있다는 가정하에 3 은 어디에 삽입되어야 할까? 인접한 원소부터 앞으로 차례차례 비교해보면 10은 3보다 크고, 그 앞에는 비교..

개념 버블 정렬은 바로 옆에 있는 값과 비교해서 우선 순위가 높은 값을 앞으로 보낸다. 예제 다음은 5개의 정수 배열 {5, 3, 4, 2, 1} 을 오름차순으로 버블 정렬하는 과정을 보여준다. 다음 그림과 같이 인접한 두 수를 비교하고 앞에 있는 수가 뒤에 있는 수보다 클 때 교환하는 과정을 반복하며 끝까지 진행하면 가장 큰 수인 5가 맨 뒤에 오게 된다. 이렇게 되면 첫 번째 순회가 끝난다. 그 이후에는 마지막 인덱스를 제외하면서 계속 순회하며 정렬하는 과정을 반복한다. 구현 class Sort { public static void bubbleSort(int[] arr) { for (int i = 1; i < arr.length; i++) { for (int j = 0; j < arr.length -..

개념 주어진 값들 중 최솟값을 선택해서 배열의 맨 앞의 값과 교환한다. 그리고 맨 앞을 제외한 나머지 중에서 최솟값을 선택하고 교환하는 과정을 반복한다. 예제 {5, 4, 3, 2, 1} 로 이루어진 배열을 오름차순으로 선택 정렬하는 순서이다. 파란색 화살표는 주어진 범위에서 최소값이 위치할 공간을 가리키며, 빨간색 화살표는 최솟값을 가리킨다. 두 화살표가 가리키는 공간에 있는 값끼리 교환(swap)이 일어난다. 코드 class Sort { public static void selctionSort(int[] arr) { int min; int idx = 0; for (int i = 0; i < arr.length; i++) { min = Integer.MAX_VALUE; for (int j = i; j ..