99클럽 코테 스터디 38일차 TIL + 정렬 알고리즘(Sort Algorithm)(1)

학습 키워드

- 정렬 알고리즘(Sort Algorithm)

 

공부한 내용

정렬 알고리즘(Sort Algorithm)

• 정렬 알고리즘(Sort Algorithm)은 데이터를 특정한 기준에 따라 순서대로 정렬하는 알고리즘을 말한다.

→ 원소들을 일정한 순서대로 열거하는 알고리즘이다.

정렬 알고리즘의 특징

순서가 바뀌지 않는다.

→ 동일한 값을 가진 요소들의 순서가 정렬 전후로 변하지 않는 특징을 가지는 것을 의미한다.

→ 동일한 값을 가진 두 요소가 정렬되기 전에는 첫 번째 요소가 두 번째 요소보다 앞에 위치하고, 정렬된 후에도 첫 번째 요소가 두 번째 요소보다 앞에 위치하게 된다.

⇒ 정렬 알고리즘이 동일한 값의 순서를 보존한다

정렬 알고리즘 - 1 : 퀵 정렬(QuickSort)

• 퀵 정렬 알고리즘은 분할 정복(Divide and Conquer) 방법을 사용하여 구현된 정렬 알고리즘을 의미한다.
• 병합 정렬은 일정한 부분 리스트로 분할하지만 퀵 정렬은 피벗이 들어갈 위치에 따라 불균형하다.
• 합병 정렬과 속도가 비슷하고 힙 정렬보다 빠르지만, 최악의 경우 O(n^2)만큼 걸린다는 점, 보통 재귀로 구현하기 때문에 메모리를 더 사용할 수 있다는 단점이 있다.
• 최악의 경우는 피봇을 최솟값이나 최댓값 으로 선택하여 부분 배열이 한쪽으로 계속 몰리는 경우이다.
• 대규모 데이터를 정렬하는 데 매우 유용하며, 많은 프로그래밍 언어에서도 내장된 정렬 함수에 사용되는 알고리즘이다.

분할 정복(Divide and Conquer)

• 큰 문제를 작은 문제로 나누어서 해결하는 알고리즘을 의미한다.
• 분할 → 정복 → 결합의 단계 처리가 된다.

1. 분할 단계에서는 문제를 작은 부분 문제들로 나누는 단계이다.
2. 정복 단계에서는 부분 문제를 해결한다.
3. 결합 단계에서는 부분 문제의 해들을 모아 원래의 문제의 해를 구하는 방식이다.

• 분할 정복 참고 사이트
• https://adjh54.tistory.com/219

퀵 정렬의 동작 방식

1. 배열에서 하나의 요소를 기준으로 선택한다. 이를 피벗(Pivot)이라고 한다.
2. 피벗을 기준으로 작은 요소는 피벗의 왼쪽으로, 큰 요소는 피벗의 오른쪽으로 분할한다.
3. 분할된 두 개의 하위 배열에 대해 재귀적으로 위의 과정을 반복한다.
4. 하위 배열이 더 이상 분할되지 않으면 정렬이 완료된다.

• 퀵 정렬에서 분할 정복 방법을 사용하여 구현되었기 때문에, 배열을 분할하고 분할된 부분 배열에 대해 재귀적으로 정렬을 수행하는 방식으로 동작한다.
• 이러한 분할 정복의 개념을 통해 퀵 정렬이 효과적으로 동작하고 배열을 정렬할 수 있다.

퀵 정렬 종류 : 일반 정렬 알고리즘(Arrays.sort(), Collections.sort())

Arrays.sort()

• 퀵 정렬을 사용하여 배열을 정렬하는데 사용되며 기본 타입 배열과 객체 타입 배열 모두에 대해 사용할 수 있다.

Collections.sort()

• 퀵 정렬를 사용하여 객체를 정렬하는데 사용되며 List, Set, Queue 등의 컬렉션 프레임워크에 사용할 수 있다.

일반 정렬 사용 예

import java.util.*;

/*
 * 숫자 배열의 정렬
 */
Integer[] sortNumArr1 = {0, 1, 2, 3, 4};
Integer[] sortNumArr2 = {10, 11, 1, 2, 4};

// [CASE1] 숫자 오름차순 정렬 -1 : 오름차순으로 정렬이 됩니다.
Arrays.sort(sortNumArr1);   // [0, 1, 2, 3, 4]

// [CASE2] 숫자 오름차순 정렬 -2 : 오름차순으로 정렬이 됩니다.
Arrays.sort(sortNumArr1, Comparator.naturalOrder()); // [0, 1, 2, 3, 4]

// [CASE3] 숫자 내림차순 정렬 -1 : 내림차순으로 정렬이 됩니다.(* 해당 주의 사항은 Wrapper Class 를 이용하여야 합니다.)
Arrays.sort(sortNumArr1, Collections.reverseOrder());   // [4, 3, 2, 1, 0]

// [CASE4] 숫자 내림차순 정렬 -2 : 내림차순으로 정렬이 됩니다.(* 해당 주의 사항은 Wrapper Class 를 이용하여야 합니다.)
Arrays.sort(sortNumArr1, Comparator.reverseOrder());   // [4, 3, 2, 1, 0]

/*
 * 문자열의 정렬-1 : 대소문자를 구분하여 정렬하는 방식
 */
String[] sortStrArr1 = {"strawberry", "Strawberry", "mango", "Mango", "cherry", "Cherry", "banana", "Banana", "apple", "Apple"};

// [CASE1] 문자 정렬 : 오름차순으로 정렬합니다.
Arrays.sort(sortStrArr1);                                           // [Apple, Banana, Cherry, Mango, Strawberry, apple, banana, cherry, mango, strawberry]

// [CASE2] 문자 정렬 : 내림차순으로 정렬이 됩니다. (* 해당 주의 사항은 Wrapper Class 를 이용하여야 합니다.)
Arrays.sort(sortStrArr1, Collections.reverseOrder());               // [strawberry, mango, cherry, banana, apple, Strawberry, Mango, Cherry, Banana, Apple]

정렬 알고리즘 - 2 : 버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

• 인접한 두 원소를 비교하여 필요한 경우 위치를 교환하여 배열을 정렬하는 방식을 의미한다.
• 해당 정렬 방식은 정렬한 원소의 개수가 적을 때나, 정렬할 원소의 개수가 많더라도 이미 거의 정렬된 상태일 때 사용될 수 있다.
• 그러나, 대부분의 경우 다른 정렬 알고리즘보다 느리고 비효율적이기 때문에, 실제로 사용되는 경우는 드물다.

→ 비교와 교환이 모두 일어날 수 있기 때문에 코드는 단순하지만 성능은 좋지 않다.

버블 정렬의 동작 방식

1. 배열의 첫 번째 요소부터 인접한 요소와 비교한다.
2. 만약 인접한 요소의 순서가 잘못되어 있다면 위치를 교환한다.
3. 배열의 끝까지 이동하면서 위의 과정을 반복한다.
4. 한 번의 반복이 끝나면 가장 큰 요소가 배열의 마지막으로 이동한다.
5. 위의 과정을 배열이 정렬될 때까지 반복한다.

 

 

 

 

참고 자료

- https://adjh54.tistory.com/334

- https://sjh9708.tistory.com/209