개인적으로 정렬은 코테에서 혹은 개발을 할때 자주 쓰인다고 생각되어서 정렬에 대해 공부를 해두고 싶었다. 그래서 이 기회에 리트코드에 있는 정렬에 대한 글을 보고 정리를 해봤다.
1.정렬의 핵심원리는 무엇일까
정렬의 문제는 어떻게 집합에 있는 아이템들을 순서대로 놓을지이다. 어떤 순서대로 놓을지는 전적으로 비교방법에 따라 달라진다. 정렬의 기초는 각각의 아이템중 공통된 특성들끼리 묶어 재배열하는 것이다. 컴퓨터 공학에서는 순서에 관한 형식이 있다. 그 형식은 다음과 같다.
전제: 만약 아이템이 a 와 b 가 주어졌다면(Law of trichotomy(=삼분법칙))
1. 아래의 연산 중 하나는 참이어야 한다.
a > b | a = b | a < b
2. 그리고 다음과 같은 식이 성립되어야 한다. (transitive relation(=추이관계))
a < b 이고 b < c 이면 a < c 이다.
정렬예시코드 - 문자열 길이순으로 정렬
import java.util.Arrays;
public class Solution {
public void sortByLength(String[] arr) {
// Sorts a list of string by length of each string
Arrays.sort(array, new StringCompare());
}
}
public class StringCompare implements Comparator<String> {
public int compare(String s1, String s2) {
if (s1.length() > s2.length()) {
return 1;
} else if (s1.length() < s2.length()) {
return -1;
}
return 0;
}
}또 하나의 중요한 개념은 반전이다. 여기서 말하는 반전은 순서와 맞지 않는 요소들의 쌍에서 일어난다. 말이 어렵지 한마디로 순서를 바꾸는것이다. 예를 들어 다음과 같은 문자열이 있다고 하자.
[“are”, “we”, “sorting”, “hello”, “world”, “learning”]
이 문자열을 위의 예제 코드처럼 길이에 따라 정렬해보자고 하자. 그럼 반전이 일어나야 된다면 반전의 경우는 이렇다.
, (“sorting”, “hello"), (“sorting”, “world”)
더 자세히는
(“are”, “we”) : [“ we”, “are ”, “sorting”, “hello”, “world”, “learning”]
(“sorting”, “hello") : [“ we”, “are”, “hello”, “sorting”, “world”, “learning”]
(“sorting”, “world”) : [“ we”, “are”, “hello”, “world”, “world sorting”, “learning”]
정렬이란 것은 다른말로 하면 이러한 반전작업의 횟수를 0인 상태로 만드는것을 말한다.
중요한 개념에는 안정성도 있다. 안정적인 정렬은 정렬기준상 동일한 요소에 대한 처리를 어떻게 하느냐에 관한 것이다.
다시 예를 들어보자, 다음과 같은 문자열 집합이 있고 문자열의 길이 순서대로 정렬을 해보자
[“hello”, “world”, “we”, “are”, “learning, “sorting”]
근데 hello 와 world의 글자수는 같다. 그런 경우 정렬은 2가지의 형태로 이루어진다.
1.[“we”, “are”, “hello”, “world”, “sorting”, “learning”]
2.[“we”, “are”, “world”, “hello”, “sorting”, “learning”]
이 중에서 원래의 순서에 가까운 1이 더 안정적인 정렬로 간주된다. (원본이 hello, world 순서이기 때문에)
2.정렬의 종류 - 비교기반 정렬
비교기반 정렬이란 정의된 순서관계를 위해 요소들의 직접적인 비교 방법이 필요한 정렬이다. 어떻게 보면 직관적으로 서로를 비교하기 때문에 더 이해하기 자연스러운 정렬 알고리즘이다. 잘 알려진 비교기반 정렬은 다음과 같다.
선택정렬, 버블정렬, 삽입정렬, 힙정렬1. 선택정렬
선택정렬은 최소값을 가진 요소를 반복해서 선택하여 정렬을 하는 방법이다.
public class Solution {
public void selectionSort(int[] arr) {
int min_index;
for (int i = 0; i < arr.length; i++) {
min_index = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
int temp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = temp;
}
}
}직관적이지만 정렬속도가 가장 느린편이다. 빅오 표기법 상 시간복잡도는 배열 안에서 배열을 한번 더 검색하기 때문에 O(n2)이며, 메모리 상에서 추가되는 것이 없기 때문에 공간복잡도는 O(1) 이다.
또 안정적인 정렬 알고리즘도 아니다. 동일한 요소의 순서를 유지하지 않기 때문이다. 예를들어보면
[ 4 , 2, 3, 4, 1] 라는 배열이 있을때 최소값을 계속 앞으로 보내게 된다면, 정렬결과는 [1, 2, 3, 4, 4 ] 이 되기 때문이다.
2.버블정렬
버블정렬은 두개의 인접한 요소를 비교한뒤 정렬이 필요하면 정렬을 한다. 정렬을 한 후 다음 인덱스로 이동하여 또 두개의 인접한 요소를 비교한다. 이러 과정을 전부다 정렬이 될 때까지 반복한다.
public class Solution {
public void bubbleSort(int[] arr) {
boolean hasSwapped = true;
while (hasSwapped) {
hasSwapped = false;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
hasSwapped = true;
}
}
}
}
}시간복잡도는 . 간단하게 구현할 수 있지만 실행속도는 가장느리다. 실행시간은 정렬에 필요한 요소에 비례한다.
선택정렬과 다르게 버블 정렬은 동일한 요소가 위치를 바꾸지 않으므로 안정적인 정렬 알고리즘이다. 하지만 간단하고 안정적인것 외에 장점이 없어 잘 쓰이지 않는다.
3.삽입정렬
삽입정렬은 버블정렬과 비슷하다. 순서대로 요소들을 검사해서 정렬 기준에 부합되지 않는다면 해당 요소를 올바른 위치로 이동시킨 후에 다음요소를 검사한다.
public class Solution {
public void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int currentIndex = i;
while (currentIndex > 0 && arr[currentIndex - 1] > arr[currentIndex]) {
// Swap elements that are out of order
int temp = arr[currentIndex];
arr[currentIndex] = arr[currentIndex - 1];
arr[currentIndex - 1] = temp;
currentIndex -= 1;
}
}
}
}마찬가지로 시간복잡도는 O(n2)이다. 안정적인 정렬이다. 시간복잡도가 앞에 두개랑 많은 차이는 없지만 배열크기에 비해 반전횟수가 상대적으로 적다면 삽입정렬은 꽤나 빨리 정렬을 수행한다. 또 작은 배열에서도 삽입정렬은 시간이 적게 쓰이는 편이다. Java에서 쓰이는 Array.sort() 메소드도 최적의 정렬을 수행하기 전에 삽입정렬을 하는게 좋은지 체크한다고 한다.
4.힙 정렬
앞에서 본 3개는 최소값을 검사해 앞으로 보내는 작업을 시행하였다. 힙 정렬은 힙 자료구조를 이용하여 정렬을 수행하는것이다. 힙 정렬의 기본 개념은 힙을 구성하고 배열을 정렬하기 위해 최소/최대요소를 반복적으로 제거하는 것이다.
public class Solution {
public void heapSort(int[] arr) {
// Mutates elements in lst by utilizing the heap data structure
for (int i = arr.length / 2 - 1; i >= 0; i--) {
maxHeapify(arr, arr.length, i);
}
for (int i = arr.length - 1; i > 0; i--) {
// swap last element with first element
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
// note that we reduce the heap size by 1 every iteration
maxHeapify(arr, i, 0);
}
}
private void maxHeapify(int[] arr, int heapSize, int index) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest != index) {
int temp = arr[index];
arr[index] = arr[largest];
arr[largest] = temp;
maxHeapify(arr, heapSize, largest);
}
}
}시간복잡도는
'프로그래밍 공부 > 알고리즘' 카테고리의 다른 글
| 정렬에 관한 정리-2 (0) | 2024.01.15 |
|---|---|
| 선택 정렬 (0) | 2020.11.03 |
