chapter 06 - 1 정렬
정렬 (sorting)
핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업
작은 것부터 큰 순서로 정렬한 경우 오름차순 정렬 (ascending order),
큰 것부터 작은 순서로 정렬한 경우 내림차순 정렬 (descending order)
정렬 알고리즘의 안정성
- 같은 값의 key를 가진 요소의 순서가 정렬의 전후에도 유지된다면 안정된 정렬이라고 함.
- 안정되지 않은 경우, 예를 들어 같은 점수인 학생끼리 이름 순 혹은 학번 순으로 자연스럽게 정렬되지 않음.
내부 정렬과 외부 정렬
- 내부 정렬 (internal sorting)
- 정렬하고자 하는 모든 데이터를 하나의 배열에 저장할 수 있는 경우 사용
- 외부 정렬 (external sorting)
- 정렬하고자 하는 데이터가 너무 많아 하나의 배열에서 작업할 수 없는 경우 사용
정렬 알고리즘의 핵심 요소
: 교환, 선택, 삽입
chapter 06 - 2 버블 정렬
버블 정렬 (bubble sort)
이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하며 정렬하는 알고리즘 (안정적)
패스 (pass) : 정렬하고자 하는 배열에서 비교, 교환하는 작업(과정)
( 수행하는 패스의 횟수는요소가 n개라면, n - 1회)
시간 복잡도 = O(n2)
버블 정렬 프로그램
import java.util.Scanner;
class BubbleSort {
static void swap(int[] a, int index1, int index2) {
int temp = a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
// 버블정렬
static void bubbleSort(int[] a, int n) {
// 패스
for (int i = 0; i < n - 1; i++)
for (int j = n - 1; j > i; j--)
if (a[j - 1] > a[j])
swap(a, j - 1, j);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("버블정렬(버전1)");
System.out.print("요소 수 : ");
int num = scanner.nextInt( );
int[] x = new int[num];
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "]");
x[i] = scanner.nextInt( );
}
bubbleSort(x, num);
System.out.println("\n오름차순 정렬 결과");
for (int i = 0; i < num; i++)
System.out.println("x[" + i + "] = " + x[i]);
}
}
- 비교 횟수는 첫 번째 패스에서 n - 1회, 두 번째에서 n - 2회, ,,, 이므로, 총 비교 횟수는 n(n - 1) / 2회
- 교환 횟수의 평균값은 비교 횟수의 절반인 n(n - 1) / 4회
- swap 메서드에서 값의 이동 횟수 : 3회
∴ 이동횟수 평균 = 3n(n - 1) / 4회
알고리즘 개선 (1)
// 버블정렬 메서드만 수정 (버전 2)
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
int exchange = 0;
// 패스
for (int j = n - 1; j > i; j--)
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
exchange++;
}
if (exchange == 0)
break;
}
}
- 교환횟수 확인하는 변수 추가하여 교환이 없다면 종료하도록 수정
알고리즘 개선 (2)
// 버블정렬 메서드만 수정 (버전 3)
static void bubbleSort(int[] a, int n) {
int k = 0;
while (k < n - 1) {
int lastChange = n - 1;
// 패스
for (int j = n - 1; j > k; j--)
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
lastChange = j;
}
k = lastChange;
}
}
- 마지막으로 교환한 위치를 lastChange 변수에 저장하여 다음 정렬 수행 시 해당 위치에서 수행하도록 수정
- 교환할 때마다 가장 오른쪽 요소의 인덱스 값을 lastChange 변수에 저장
chapter 06 - 3 단순 선택 정렬
단순 선택 정렬 (straight selection sort)
가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘
(서로 떨어져 있는 요소를 교환하기 때문에 불안정함)
교환 과정
① 정렬되지 않은 부분에서 가장 작은 값을 선택 (a[min])
② 정렬되지 않은 부분의 첫 번째 요소와 a[min]의 값과 교환
시간 복잡도 = O(n2)
단순 선택 정렬 메서드
static void selectionSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
swap(a, i, min);
}
}
- 비교 횟수 : (n2 - n) / 2회
chapter 06 - 4 단순 삽입 정렬
단순 삽입 정렬 (straight insertion sort)
선택한 요소를 더 앞쪽의 알맞은 위치에 삽입하는 작업의 반복으로 정렬하는 알고리즘
(떨어져 있는 요소들이 바뀌는 것이 아니라 안정적)
아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입
( 2번째 요소부터 선택하여 진행함)
두 조건 중 만족하는 위치에 값 대입
① 정렬된 열의 왼쪽 끝에 도달
② temp값보다 작거나 같은 key를 갖는 항목 발견
시간 복잡도 = O(n2)
단순 삽입 정렬 프로그램
import java.util.Scanner;
class InsertionSort {
// 단순 삽입 정렬
static void insertionSort(int[] a, int n) {
for (int i = 1; i < n; i++) {
int j;
int temp = a[i];
for (int j = i; j > 0 && a[j - 1] > temp; j--)
a[j] = a[j - 1];
a[j] = temp;
}
}
public static void main(Stirng[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("단순 삽입 정렬");
System.out.print("요소 수 : ");
int num = scanner.nextInt( );
int[] x = new int[num];
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "] : ");
x[i] = scanner.nextInt( );
}
insertionSort(x, num);
System.out.println("\n오름차순 정렬 완료");
for (int i = 0; i < num; i++)
System.out.println("x[" + i + "] = " + x[i]);
}
}
- 비교 횟수와 교환 횟수 : n2 / 2회
'Android ᙏ̤̫͚ > JAVA Algorithm' 카테고리의 다른 글
Chapter 05. 재귀 알고리즘 (0) | 2021.01.16 |
---|---|
Chapter 04. 스택과 큐 (0) | 2021.01.13 |
Chapter 03. 검색 (0) | 2021.01.13 |
Chapter 02. 기본 자료구조 (0) | 2021.01.10 |
Chapter 01. 기본 알고리즘 (0) | 2021.01.08 |