정렬/탐색

1. 정렬

여러 가지 데이터를 특정 기준에 의해 내림차순/오름차순으로 정렬한다. 여기서는 정수형 데이터를 오름차순으로 정렬한다고 가정한다.

​

선택정렬

정렬되지 않은 목록에서 가장 큰 수를 찾아 목록의 맨 뒤로 옮기는 것을 반복하는 정렬 방법이다.

 

 

삽입정렬

배열의 앞에서부터(이때 이 부분은 정렬되어 있음) 하나씩 인덱스를 늘려가며 새로운 데이터를 기존 정렬된 부분에 순서에 맞추어 끼워넣는 방법이다. 정렬 시작시 "정렬된 부분"은 가장 빠른 인덱스 하나로 정의하고 값이 하나이므로 정렬되었다고 본다.

​

삽입정렬의 알고리즘은 쉽지만 본인은 이걸 코드로 직접 구현할때 조금 헷갈려했는데, 새로운 데이터를 삽입하기 전 기존 데이터를 한칸씩 shifting 시키는것이 조금 헷갈렸다. 혹시나 마찬가지인 사람은 주석을 잘 읽어보셈

 

 

버블정렬

배열의 시작점부터 2개의 원소를 비교하여 정렬 기준에 맞게 데이터 교환이 필요하면 교환한다. 배열의 끝까지 도달했다면 다시 배열의 시작점으로 돌아가 같은 과정을 수행한다. 단 이때 배열의 끝 인덱스-1 까지만 정렬하며, 이후 계속해서 반복한다.

버블정렬 알고리즘

버블정렬은 과정이 많기 때문에 그냥 위키에서 퍼온걸로 대체한다. (Bubble sort - Wikipedia)

 

 

퀵정렬​

퀵정렬은 주어진 배열 중 하나의 데이터를 선택하여 나머지 데이터들을 미리 선택한 데이터(기준점, pivot 이라고도 함)를 기준으로 작은 그룹 및 큰 그룹으로 분리하는 과정을 반복하는 정렬 방법이다. 일반적으로 매우 빠르게 작동하는 정렬 방법이지만, 구현의 난이도가 조금 있는 편이다

퀵정렬 알고리즘

주어진 배열에서 기준점(pivot)을 하나 선택하고 기준보다 작은 그룹과 큰 그룹으로 분리하는 과정을 계속 반복한다. 이것은 매우 추상적인 서술이기 때문에, 구체적으로 위 과정을 어떻게 수행하는지를 알아야 한다. 여러가지 방법이 있으며, 아래의 과정은 위키피디아를 참고하여 작성하였다. (단 피벗은 그냥 맨 오른쪽으로 설정함. 위키는 가운데)

​

퀵정렬 알고리즘 - 더 구체적으로

1. 배열의 원소들을 피벗값보다 큰 값/ 작거나 같은 값으로 분류하기

1-1. 배열의 오른쪽 끝 원소를 피벗으로 설정한다.

1-2. 피벗을 제외한 배열에서 왼쪽 끝 값의 인덱스를 left, 오른쪽 끝 값의 인덱스를 right로 설정한다.

1-3. 이제 left값을 하나씩 증가시키며 피벗보다 크거나 같은 값을 찾아낸다.(left값의 증가로 시작하는 이유는 피벗이 오른쪽에 위치하기 때문)

1-4. 조건을 만족하는 left값을 찾았으면 right값을 감소시키며 피벗보다 작은 값을 찾아낸다.

1-5. 조건을 만족하는 두 값을 찾았으면 left<right 임을 확인한 후 맞다면 두 값을 교환한다.

​

2. 피벗 값을 올바른 위치로 이동시키기

인덱스 left와 right의 위치가 바뀌면 모든 비교가 끝났다는 뜻이므로 피벗 원소와 list[left]를 교환한다. (비교가 끝나면 list[right]는 피벗보타 크거나 같음이 확실하다.)

​

3. 나누어진 배열들에 대해 recursion call을 통해 같은 과정 반복하기

나누어진 배열들의 크기가 1이 아니라면 left와 right 인덱스를 재설정한후 각각 recursion 해준다.

​

​

 

 

 

 

2. 탐색

여러 가지 데이터로 이루어진 집합에서 특정 데이터의 존재여부와 위치를 찾는다. 여기서는 배열을 사용하며 인덱스를 반환한다.

 

선형탐색

선형탐색은 가장 단순한 탐색 방법으로, 그냥 배열의 끝에서 끝까지 데이터를 검사하며 찾고자 하는 데이터가 발견되면 해당 데이터의 인덱스를 반환한다. 정렬되지 않은 배열에도 사용이 가능하지만, 속도가 느리다.

 

이진탐색

이진 탐색이란 정렬된 데이터에만 사용 가능한 탐색 방법으로, 속도가 빠르다는 장점이 있다.

알고리즘은 매우 간단한데, 정렬된 데이터에서 가장 왼쪽 인덱스(low)와 가장 오른쪽 인덱스(high)의 중앙에 위치한 값과 찾고자 하는 값을 비교한다. 이때 찾고자 하는 값이 중앙값보다 작다면 인덱스 0과 중앙 인덱스 -1 의 중앙값을 비교한다. (반대의 경우에는 반대로) 이 과정을 반복하다 보면 low 인덱스와 high 인덱스가 교차하거나(즉 탐색이 끝남) 찾고자 하는 값==중앙값 이 되어 탐색이 종료된다.

이진탐색 알고리즘

 

---

참고 자료

Quicksort Algorithm – C++, Java, and Python Implementation – Techie Delight

퀵 정렬 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

Binary search algorithm - Wikipedia