[정렬]단순선택정렬_단순삽입정렬

1. 단순 선택 정렬

straight selection sort
가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

▶︎ 단순 선택 정렬의 교환 과정

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값을 선택한다.
2. 선택한 값과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.
3. 1-2번의 과정을 n - 1회 반복한다.

package com.study.Algorithm;
import java.util.Scanner;
// 단순 선택 정렬

class SelectionSort {
	// 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
	static void swap(int[] arr, int idx1, int idx2) {
		int temp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = temp;
	}

	// 단순 선택 정렬
	static void selectionSort(int[] arr, int n) {
		for (int i = 0; i < n - 1; i++) {
			int min = i;			// 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록합니다.
			for (int j = i + 1; j < n; j++)
				if (arr[j] < arr[min])
					min = j;
			swap(arr, i, min);		// 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환합니다.
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		System.out.println("단순 선택 정렬");
		System.out.print("요솟수：");
		int nx = sc.nextInt();
		int[] arr = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.print("arr[" + i + "]：");
			arr[i] = sc.nextInt();
		}

		selectionSort(arr, nx);			// 배열x를 단순선택정렬

		System.out.println("오름차순으로 정렬했습니다.");
		for (int i = 0; i < nx; i++)
			System.out.println("arr[" + i + "]＝" + arr[i]);
	}
}

단순 선택 정렬 알고리즘은 서로 떨어져 있는 요소를 교환하는 것이기 때문에, 안정적이지 않다.

 

 

 

2. 단순 삽입 정렬

straight insertion sort
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하여 정렬

• 트럼프 카드를 한 줄로 늘어놓을 때 사용하는 방법과 비슷한 방법의 알고리즘
• 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입

▶︎ 알맞은 위치에 삽입? 
- 오름차순 정렬
- 오른쪽 끝부터 왼쪽으로 정렬 정렬할 요소를 선택.
- 편하게 a요소라고 하자.

1. 선택된 a요소의 이웃한 요소1과 비교하여, 이웃한 요소1이 크면 a요소의 자리에 이웃한 요소1을 대입한다.
2. 이때 a요소의 값은 다른곳에 저장해두어야 한다.
3. a요소와 다음 요소를 비교하여 1번의 작업을 반복합니다.
4. a요소와 비교하는 요소 중 a요소가 더 큰 값을 만나면, 비교 요소의 인덱스 값 +1인 자리에 a요소의 값을 대입합니다.

▶︎ 삽입이 완료되어 정렬될 때의 조건
1. 정렬된 열의 왼쪽 끝에 도달합니다.
2. 요소 a보다 작거나 같은 key를 갖는 항목을 발견합니다.

▶︎ 드모르간 법칙을 적용하자
- 왜 드모르간을 쓰는가 고민해보기
- 요소 a의 값을 arr[a]라고 하고, 반복 제어용 번수 i에 a - 1의 값을 대입했다고 하자.
- 드모르간 법칙 적용시의 반복 완료 조건
   1. i가 0보다 크다
   2. arr[a-1]의 값이 arr[a]보다 크다.

package com.study.Algorithm;
import java.util.Scanner;
// 단순 삽입 정렬

class InsertionSort {
	// 단순 삽입 정렬
	static void insertionSort(int[] arr, int n) {
		for (int i = 1; i < n; i++) {
			int j;
			int temp = arr[i];
			for (j = i; j > 0 && arr[j - 1] > temp; j--)
				arr[j] = arr[j - 1];
			arr[j] = temp;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		System.out.println("단순 삽입 정렬");
		System.out.print("요솟수：");
		int nx = sc.nextInt();
		int[] arr = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.print("arr[" + i + "]：");
			arr[i] = sc.nextInt();
		}

		insertionSort(arr, nx);				// 배열 x를 단순 삽입 정렬

		System.out.println("오름차순으로 정렬했습니다.");
		for (int i = 0; i < nx; i++)
			System.out.println("arr[" + i + "]＝" + arr[i]);
	}
}

 

▶︎ 단순 정렬의 시간 복잡도

• 버블 정렬, 단순 선택 정렬, 단순 삽입 정렬 모두 단순 정렬
• 단순 정렬의 시간 복잡도는 모두 O($n^2$)

 

[자료출처:www.notion.so/b1afde9993c6462892ad9ec8fc176103]