/Algorithm/ 💬 정렬

1. 정렬알고리즘

---

정렬

---

• 안정된 정렬

  키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것

• 안정되지 않은 정렬

  키값이 같은 요소의 순서가 정렬 전후에도 유지되지 않는 것

• 내부 정렬

  정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 사용하는 알고리즘

• 외부 정렬

  정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘

• 정렬 알고리즘의 핵심 요소

  교환, 선택, 삽입
  대부분의 정렬 알고리즘은 이 3가지 요소를 응용한 것

2. 버블 정렬

---

bubble sort

• 단순 교환 정렬(straight exchange sort)
• 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘

버블 정렬 프로그램 만들기

---

// 버블 정렬(단순 교환 정렬) (버전 1)

import java.util.Scanner;

class BubbleSort {

	/*
	버블정렬
	 */
	static void bubbleSort(int[] a, int n) {
		// 숫자는 n개, 패스 횟수는 n-1번
		// 첫 번째 패스의 비교 횟수는 n - 1, 두 번째 패스의 비교 횟수는 n - 2회 ...
		// a[i], a[i + 1], …, a[n - 1]
		for (int i = 0; i < n - 1; i++) // 인덱스 i ~ n-1까지 반복
			// 패스 : 두개씩 비교해 한줄 통과할 때
			for (int j = n - 1; j > i; j--) // 맨뒤 인덱스 n-1부터 시작해서 앞으로 2개씩 비교
				if (a[j - 1] > a[j])
					swap(a, j - 1, j);
	}

	/*
	배열 요소 a[idx1]와 a[idx2]의 값 교환
	 */
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
	}

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

		System.out.println("버블 정렬(버전 1)");
		System.out.print("요솟수: ");
		int nx = stdIn.nextInt();
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.print("x[" + i + "]: ");
			x[i] = stdIn.nextInt();
		}

		bubbleSort(x, nx);                // 배열 x를 단순교환정렬

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

알고리즘 개선하기 1

---

알고리즘 개선하기2

---

3. 단순 선택 정렬

---

4. 단순 삽입 정렬

---

단순 정렬의 시간 복잡도

---

5. 셸 정렬

---

단순삽입 정렬의 특징

---

셸 정렬

---

증분값(h값) 선택하기

---

6. 퀵 정렬

---

퀵 정렬 살펴보기

---

배열을 두 그룹으로 나누기

---

퀵 정렬 구현하기

---

퀵 정렬에서 배열을 나누는 과정 출력하기

---

비재귀적인 퀵 정렬 구현하기

---

스택의 크기 구하기

---

방법1. 요솟수가 많은 그룹을 먼저 푸시하는 경우

방법 2. 요솟수가 적은 그룹을 먼저 푸시하는 경우

피벗 선택하기

---

퀵 정렬의 시간 복잡도 구하기

---

7. 병합 정렬

---

7-1. 정렬을 마친 두 배열의 병합 살펴보기

---

7-2. 병합 정렬 구현하기

---

병합정렬 알고리즘

---

7-3. Arrays.sort로 퀵 정렬과 병합 정렬하기

---

기본 자료형 배열의 정렬(퀵 정렬)

---

클래스 객체 배열의 정렬(병합정렬)

---

자연그러운 순서를 갖고 있지 않은 배열의 정렬 만들기

---

8. 힙 정렬

---

8-1. 힙이란?

---

트리

---

8-2. 힙 정렬 알아보기

---

루트를 없애고 힙 상태 유지하기

---

힙 정렬 알고리즘 살펴보기

---

8-3. 배열을 힙으로 만들기

---

downHeap 메서드

---

heapSort 메서드

---

힙 정렬의 시간 복잡도

---

9. 도수 정렬

---

9-1. 도수정렬 알아보기

---

1단계: 도수분포표 만들기

---

2단계: 누적분포표 만들기

---

3단계: 목표배열 만들기

---

4단계: 배열 복사하기

---

---

(참고)

• Java - 배열 정렬(Sorting) (오름차순, 내림차순)

공부한 내용을 여러글과 책 읽은 내용을 바탕으로 정리하고 있습니다.
좋은 글로 저의 공부에 도움을 주시는 분들께 감사드립니다.