[정렬] Bubble, Selection, Quick Sort 정리

1. Bubble sort

위키피디아

gyoogle.dev

인접한 두 원소를 비교하여, 교환 및 정렬하는 알고리즘

1. Selection Sort와 유사한 알고리즘
2. 이름이 Bubble Sort인 이유: 거품처럼 수면으로 올라오는 듯한 모습

1. 1 Bubble Sort 과정

1. 배열을 순회하며, [첫 번째 원소 ↔️ 두 번째 원소], [두 번째 원소 ↔️ 세 번째 원소] ...  [마지막 - 1 원소 ↔️ 마지막 원소] 를 비교하며 교환
2. 순회를 1회 반복하면, 배열의 1개의 원소가 정렬된다. 따라서 1번 과정을 N-1번 반복. 

1. 2 코드

import java.util.Arrays;
import java.util.Random;

public class 자바연습장{
    public static void main(String[] args) {
        System.out.println("asd");
        
        int[] randomIntArr = new int[100];
        
        createRandInt(randomIntArr);
        bubbleSort(randomIntArr);

        System.out.println(Arrays.toString(randomIntArr));
    }
    
    static void createRandInt(int[] arr){
        Random rand = new Random();

        for(int i = 0; i < arr.length; i++){
            arr[i] = rand.nextInt() % 100;
        }
    }
    
    static void bubbleSort(int[] arr){
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr.length - i -1; j++){
                if( arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

1. 3 복잡도

1. 시간 복잡도
   O(N^2)
2. 공간 복잡도
   O(N)

1. 4 장단점

• 장점
  
  1. 구현이 매우 간단, 직관적
  2. 정렬하고자 하는 배열 안에서 교환 ➡️ 다른 메모리 공간 필요 없음! 
     = 제자리 정렬(in-place sorting)
  3. 안정 정렬(Stable Sort)

• 단점
  1. 시간복잡도가 항상 O(N^2) ➡️ 매우 비효율
  2. 교환 연산(swap)이 많이 일어난다.

제자리 정렬?
추가적인 메모리 공간 없이, 입력 배열 자체로 정렬하는 방식. ➡️ 입력 배열을 수정하여 정렬.
장점 : 메모리 사용량이 적음 

제자리 정렬 알고리즘의 종류
Bubble Sort, Selection Sort, Insertion Sort, Quick Sort 등

안정 정렬? 
동일한 값의 데이터는 순서를 바꾸지 않음 ( 정렬할 필요가 없으면 그대로 둠)

안정 정렬 알고리즘의 종류
Insertion Sort, Bubble Sort, Merge Sort, Counting Sort, Radix Sort 등

---

2. Selection Sort

위키피디아 선택정렬

gyoogle.dev 선택 정렬

첫 번째 인덱스부터 순차적으로 어떤 원소를 넣을 지, 선택하는 알고리즘.

Selection Sort vs Insertion Sort
Selection Sort는 배열에서 자리를 먼저 선택 후, 그 자이레 오는 값을 찾음.
Insertion Sort

2. 1 Bubble Sort 과정

1. 배열의 첫 번째 인덱스부터 하나 선택
2. 그 뒤에 위치한 값들 중 최소값을 찾음
3. 1번에서 선택한 인덱스와 최소값을 교체
4. 1~3을 모든 인덱스에 대해 반복

2. 2 코드

//java
import java.util.Arrays;
import java.util.Random;

public class 정렬들{
    public static void main(String[] args) {
      
        int[] randomIntArr = new int[100];
        
        createRandInt(randomIntArr);

        System.out.println("---- Selection Sort ----");
        SelectionSort(randomIntArr);

        System.out.println(Arrays.toString(randomIntArr));
    }
    
    static void createRandInt(int[] arr){
        Random rand = new Random();

        for(int i = 0; i < arr.length; i++){
            arr[i] = rand.nextInt() % 100;
        }
    }
    
    static void SelectionSort(int[] arr){
        for(int i = 0; i < arr.length-1; i++){
            int indexMin = i;
            for(int j=i+1; j<arr.length; j++){
                if(arr[indexMin] > arr[j]){
                    indexMin = j;
                }
            }
            
            int temp = arr[i];
            arr[i] = arr[indexMin];
            arr[indexMin] = temp;
        }
    }
}

2. 3 복잡도

1. 시간복잡도
   O(N^2)
2. 공간복잡도
   O(N)

2. 4 장단점

• 장점
  1. 단순하다
  2. Bubble Sort보다 교환 횟수가 적음 ➡️ 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적임
  3. 제자리 정렬(In-place Sort)
• 단점
  1. 시간복잡도가 비효율적
  2. 불안정 정렬(Unstable Sort)

불안정 정렬(Unstable sort)
안정 정렬과는 반대로, 값은 값을 가지는 요소들도 교환이 일어남. 
즉, 원본 순서의 보장이 안됨.

불안정 정렬 알고리즘 종류
Selection Sort, Quick Sort, Heap Sort ... 등

 

 

3 Quick Sort

• 분할 정복을 통해 정렬하는 기법
• 불안정 정렬
• 배열을 비균등하게 분할

3. 1 Bubble Sort 과정

위키피디아

1. 하나의 원소를 피벗으로 고름
2. 피벗 앞에는 피벗보다 작은 값, 피벗 뒤에는 피벗보다 큰 값이 오도록 배열을 둘로 나눔.
3. 1번과 2번을 재귀적으로 반복

참고 출처 

https://ko.wikipedia.org/

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html