루바의 여정

퀵 정렬 정렬 알고리즘 중에서 가장 많이 사용되는 알고리즘이며 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. 퀵 정렬은 '피벗'이라는 기준을 가지고 피벗보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법을 사용한다. 동작 방법은 아래와 같다. 1. 리스트에서 첫 번째 데이터를 피벗으로 설정한다. 2. 리스트의 왼쪽에서부터 피벗보다 큰 데이터를 찾는다. 3. 리스트의 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 4. 작은 데이터와 큰 데이터가 서로 엇갈린 위치에서 발견되었다면 작은 데이터와 피벗의 위치를 바꾼다. 5. 엇갈리지 않았다면 작은 데이터와 큰 데이터의 위치를 바꾼다. 예시 숫자 10, 20, 6, 39, 40, 1, 16, 9가 순서대로 저장되어 있다. 리스트의 첫 ..

계수 정렬(Count Sort) 특정한 조건이 부합할 때만 사용할 수 있는 정렬 방법이다. 하지만 매우 빠른 속도를 가지고 있다. 여기서 특정한 조건은 아래와 같다. 1. 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있다. 2. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다. 계수 정렬은 가장 큰 데이터와 가장 작은 데이터 차이만큼의 크기를 갖는 리스트를 선언해야 하기 때문에 위와 같은 특정한 조건을 갖는다. 즉, 계수 정렬은 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 특징이 있다. 계수 정렬은 모든 범위를 포함하는 인덱스를 갖는 리스트를 생성한 후, 앞에서부터 데이터를 읽어나가며 해당하는 데이터에 맞는 인덱스에 1을 추가한다. 예시 숫..

삽입 정렬(Insertion Sort) 리스트가 정렬된 부분과 정렬 안된 부분으로 나뉜다. 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 '삽입'하는 방식의 알고리즘이다. 선택 정렬에 비해 구현 난이도가 높지만, 일반적으로 더 효율적으로 동작한다. 동작 방법 숫자 4, 3, 40, 5, 23, 18, 1 이 순서대로 준비되어 있다. 1) 첫 번째 원소 '4'는 정렬되어 있다고 판단하고, 두 번째 원소인 '3'이 어떤 위치로 들어갈지 판단한다. 화살표가 들어갈 수 있는 위치이고 빨간색 화살표가 들어가야하는 위치이다. 2) 이어서 '40'이 어떤 위치로 들어갈 지 판단한다. 원래 자리가 '40'이 들어갈 자리이다. 3) 이어서 '5'가 어떤 위치로 들어갈 지 판단한다. 4) 마지막으로 '1..

선택 정렬(Selection Sort) 리스트에서 아직 정렬 안된 부분의 원소들 중에서 최솟값을 '선택'하여 정렬 안된 부분의 가장 왼쪽의 원소와 교환하는 정렬 알고리즘. 동작 방법 숫자 20, 4, 2, 1, 50, 31, 13, 7 이 준비되어 있다. 정렬된 데이터는 색으로 표시한다. 1) 정렬되지 않은 원소 중 가장 작은 '1'을 선택해 정렬 안된 부분의 가장 왼쪽에 있는 '20'과 교환해준다. 교환된 '1'이 가장 왼쪽에 위치하고 '20'은 '1'의 자리에 들어있다. 2) 정렬되지 않은 원소 중 가장 작은 '2'를 선택해 정렬 안된 부분의 가장 왼쪽에 있는 '4'와 교환해준다. 교환된 '2'가 '1' 다음에 정렬되고 '4'는 '2'의 자리에 들어있다. 3) '4'는 정렬되지 않은 수 중에서 가장 ..