정렬이란?
원소들을 기준에 맞춰 순서대로 위치시키는 것
정렬의 중요성에 대해 생각해본 결과
원하는 데이터를 탐색하는데에 있어서 용이한 정렬은 프로그래밍 및 알고리즘 이해에 도움이 된다는 것이었다. 예를들어 시간복잡도 개념과 for문에 대한 이해도 정도가 되겠다.
알고리즘 복잡도
입력 크기에 따른 단위 연산의 수행 횟수 변화를 함수로 나타낸 것을 의미한다.
알고리즘의 복잡도를 나타낼 땐, 점근적 표기(시간 복잡도 함수를 원소로 표현하는 법)를 사용한다.
점근적 복잡도 : 입력의 크기가 충분히 클 때의 복잡도
입력의 크기가 작으면 복잡한 알고리즘이든 효율적인 알고리즘이든 실제 수행 시간은 별 차이 없다.
점근적 복잡도에 있어서는 최고차항의 차수만 중요하고 나머지는 다 무시된다.
그 이유는 차수의 차이에 비하면 계수의 차이는 미미하기 때문이다.
최고 차항이 아닌 항들도 영향이 미미하기는 마찬가지이다.결론적으로 복잡도라 함은 어떤 알고리즘이 효율적인지를 판단하는 지표로 이해하면 편하다.
대표적인 점근적 표기법
빅오 표기(O) : 점근적 상한 (최악의 경우의 복잡도)
오메가 표기(Ω) : 점근적 하한 (최적의 경우의 복잡도)
세타 표기(Θ) : 점근적 동일 (평균적인 복잡도)빅오 표기법(Big-O notation)은 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법이다.
빅오 표기법이 가장 많이 사용되는 이유는 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다.
다시 말해 최악의 경우를 고려하는 데 가장 좋은 표기법이다
(알고리즘 효율성은 값이 클수록, 즉 그래프가 위로 향할수록 비효율적임을 의미)최악의 경우를 고려하는 이유는 알고리즘이 복잡해짐에 따라 평균을 구하기 애매하여,
보통 최악의 경우인 빅오 표기법이 시간복잡도에 많이 사용된다.
선택 정렬
배열에서 가장 큰 원소를 찾아 배열의 맨 끝자리 원소와 자리를 바꾼다.
이처럼 맨 우측부터 자리를 잡아가며 같은 작업을 반복한다.
private static void selectionSort(Integer[] a, int size) {
// 사이즈가 10인 배열이 존재할 때,
// [시작] 0번째 인덱스
// [종료] 8번째 인덱스
for (int i = 0; i < size - 1; i++) {
int min_index = i;
// 사이즈가 10인 배열이 존재할 때,
// [시작] 바깥 for문 시작 인덱스 + 1
// [종료] 9번째 인덱스
for (int j = i + 1; j < size; j++) {
// 만약 바깥 인덱스+1 데이터가 바깥 인덱스 데이터보다 작다면 [최소 인덱스 변수]값을 바깥인덱스+1값으로 변환한다.
// a[j] : 내부 for문 내 인덱스 값
// a[min_index] : 가장 작은 값을 가진 인덱스
if (a[j] < a[min_index]) {
min_index = j;
}
}
// i번째 값과 찾은 최솟값을 서로 교환
// 바깥 for문의 인덱스값에 가장 최저값을 swap 메서드를 통해 교환
// 이로써 0번째 인덱스부터 차차 작은 값이 위치하게 된다.
swap(a, min_index, i);
}
}
버블 정렬
한 번 돌 때마다 마지막 요소가 정렬되는 것이 거품이 올라오는 것처럼 보여 버블 정렬이라고 한다.
정렬할 배열이 주어지면, 왼쪽부터 시작한다.
이후 이웃한 쌍을 2개씩 비교해나아간다.
순서대로 되어있지 않다면 자리를 바꾼다.
위 작업을 반복하며 나아가다, 맨 오른쪽 수의 경우 대상에서 제외한다.
마지막에는 0,1번째 인덱스를 비교하며 정렬이 완료된다.
private static void bubbleSort(Integer[] a, int size) {
// 사이즈가 10인 배열이 존재할 때,
// [시작] 1번째 인덱스
// [종료] 9번째 인덱스
for (int i = 1; i < size; i++) {
// 사이즈가 10인 배열이 존재할 때,
// [시작] 0번째 인덱스
// [종료] 배열의 크기 - 바깥 for문의 초기식 변수
for (int j = 0; j < size - i; j++) {
// 처음 for문이 도는 경우
// 만약 0번째 인덱스값이 1번째 인덱스값보다 클 경우
// 1번째 인덱스가 0번째 인덱스값으로 교환
// 이로써 큰 수가 뒤에 위치하게 된다.
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}삽입 정렬
이미 정렬된 배열에서 자기 자신의 자리를 찾아서 삽입된다고 하여 삽입 정렬이라고 한다.
매 순서마다 해당 요소를 앞의 정렬된 배열에서 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.
해당 위치에 있던 요소부터 뒤의 요소들은 한 칸씩 밀린다.
private static void insertionSort(Integer[] a, int size) {
// 사이즈가 10인 배열이 존재할 때,
// [시작] 1번째 인덱스
// [종료] 9번째 인덱스
for (int i = 1; i < size; i++) {
// 처음 수행 시 1번째 인덱스 원소를 target 변수에 초기화
int target = a[i];
// 변수 j는 바깥 for문 초기식 변수보다 1이 작다.
// 처음 수행 시 0번째 인덱스을 의미한다.
int j = i - 1;
// 변수 j의 값이 0 이상이고,
// 바깥 for문 초기식 변수 인덱스의 값이, 1값을 뺀 인덱스 값보다 작을 경우
// 이전 원소값들을 한 칸씩 뒤로 미룬다.
// 그 후 j의 값을 하나 감소시킨다.
while (j >= 0 && target < a[j]) {
a[j + 1] = a[j];
j--;
}
// 위 while문을 빠져나오는 경우는 앞의 원소가 타겟(바깥 for문 초기식 변수 원소)보다 작다는 뜻으로,
// 타겟 원소는 j번째 원소 뒤에 와야한다.
a[j + 1] = target;
}
}삽입 정렬의 경우 코드만으로 이해가 어려울 수 있어 아래의 간단한 로그를 출력해보았다.
정렬 작업 전
1 5 7 8 6 4 2 3 9
================= 바깥 for문 시작, i : 1 =================
target : 5, a[i] : 5
a[j+1] : 5
================= 바깥 for문 시작, i : 2 =================
target : 7, a[i] : 7
a[j+1] : 7
================= 바깥 for문 시작, i : 3 =================
target : 8, a[i] : 8
a[j+1] : 8
================= 바깥 for문 시작, i : 4 =================
target : 6, a[i] : 6
j : 3, target : 6, a[j] : 8
j : 2, target : 6, a[j] : 7
a[j+1] : 6
================= 바깥 for문 시작, i : 5 =================
target : 4, a[i] : 4
j : 4, target : 4, a[j] : 8
j : 3, target : 4, a[j] : 7
j : 2, target : 4, a[j] : 6
j : 1, target : 4, a[j] : 5
a[j+1] : 4
================= 바깥 for문 시작, i : 6 =================
target : 2, a[i] : 2
j : 5, target : 2, a[j] : 8
j : 4, target : 2, a[j] : 7
j : 3, target : 2, a[j] : 6
j : 2, target : 2, a[j] : 5
j : 1, target : 2, a[j] : 4
a[j+1] : 2
================= 바깥 for문 시작, i : 7 =================
target : 3, a[i] : 3
j : 6, target : 3, a[j] : 8
j : 5, target : 3, a[j] : 7
j : 4, target : 3, a[j] : 6
j : 3, target : 3, a[j] : 5
j : 2, target : 3, a[j] : 4
a[j+1] : 3
================= 바깥 for문 시작, i : 8 =================
target : 9, a[i] : 9
a[j+1] : 9
정렬 작업 후
1 2 3 4 5 6 7 8 9
Process finished with exit code 0
정렬 알고리즘의 장, 단점
선택 정렬
장점 : 구현이 간단하고, 비교하는 과정에 비해 실제 교환 횟수는 적어서 많은 교환 횟수를 요하는 자료 상태에서 효율적이다.
단점 : 데이터의 개수가 많아질 시 성능이 떨어진다.
버블 정렬
장점 : 구현이 간단하다.
단점 : 데이터의 개수가 많아질 시 성능이 떨어진다.
삽입 정렬
장점 : 구현이 간단하고 데이터가 이미 정렬되어 있을 경우 성능이 좋다
단점 : 입력 데이터가 역순으로 정렬되어 있을 때 성능이 좋지 않다.
