거품 정렬 (Bubble Sort) /삽입 정렬 (Insertion Sort) / 선택 정렬 (Selection Sort)

거품 정렬 (Bubble Sort)

- 인접한 두 수를 비교, 뒤의 값이 작을 경우 swap, 값이 클 경우 다음 인접한 두 수를 비교 하여 정렬하는 방식

Java 구현

public class BubbleSort {
  public void bubbleSort(int a[]) {
            if(a.length < 1){
            return;
        }
        for(int i = 0; i < a.length; i ++) {
            for(int j = 0; j < a.length -1; j ++) {
                if(a[j] > a[ j + 1 ]) {
                    swap(a, j, j + 1);
                }
            }            
        }
    }
   public  void swap(int a[], int idx1, int idx2) {
        int temp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = temp;
    }
  
    public static void main(String args[]) {
        BubbleSort bubble = new BubbleSort();
        bubble.bubbleSort(new int[]{1,30,20,5,4,10,12});
    }
}
 

시간 복잡도

- 앞에 정렬된 값을 제외한 값을 계속 비교하여 정렬하기 때문에 n(n-1)/2

- 최선의 경우 비교만 진행 n(n-1)/2

- 최악의 경우 비교 n(n-1)/2번 비교 후 swap을 진행 하기 때문에 n(n-1)/2번이 추가됨

- 따라서 O(n^2)의 값을 같는다. 

---

삽입 정렬 (Insertion Sort)

- 처음 부터 차례로 이미 정렬된 앞 부분과 비교하여 자신의 위치를 삽입하는 정렬

예제

31	25	12	22	11			처음 상태
31	[25]	12	22	11			두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<25>	31	[12]	22	11			세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<12>	25	31	[22]	11			네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
12	<22>	25	31	[11]			마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<11>	12	22	25	31			종료.

출처: https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

Java 구현

public class InsertionSort {
    public void insertionSort(int[] arr) {
        int temp = 0;
          int j = 0; 
        for(int i = 1; i < arr.length; i++){
            temp = arr[i];
            for(j = i - 1; j >= 0 && temp < arr[j]; j--){
                arr[j + 1] = arr[j];
             }
            arr[j + 1] = temp;
      } 
    }
 
    public static void main(String[] args) {
            InsertionSort insertion = new InsertionSort();
      insertion.insertionSort(new int[]{30,20,1,4,-3,100,20,30});
    }
}
 
 

출처: http://hahahoho5915.tistory.com/8

시간 복잡도

개의 데이터가 있을 때, 최악의 경우는 ${\displaystyle \sum _{i=1}^{n-1}{i}=1+2+3+4+\cdots +(n-1)={\frac {n(n-1)}{2}}}$번의 비교를 하게 되므로, 시간복잡도는 ${\displaystyle O(n^{2})}$이 된다.

출처: https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

---

선택 정렬 (Selection Sort)

- 주어진 array에서 최솟값을 선택, 맨앞과 swap

- 맨 처음을 제외한 나머지 값 중 최솟값을 선택 하여 2번째 값과 swap

- 위의 과정을 반복한다. 

예제

패스	테이블	최솟값
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8

Java 구현

public class SelectionSort {
    public void selectionSort(int[] arr) {
        int indexMin, temp;
      for (int i = 0; i < arr.length - 1; i++) {
          indexMin = i;
          for (int j = i + 1; j < arr.length; j++) {
              if (arr[j] < arr[indexMin]) {
                  indexMin = j;
              }
          }
          temp = arr[indexMin];
          arr[indexMin] = arr[i];
          arr[i] = temp;
      }
    }
 
    public static void main(String[] args) {
            SelectionSort sort = new SelectionSort();
      sort.selectionSort(new int[]{30,20,1,4,-3,100,20,30});
    }
}
 
 

시간 복잡도

- 개의 데이터가 있을 때, 최악의 경우는 기준 값 부터 끝까지 번의 비교를 하게 되므로, 시간복잡도는 이 된다. 

출처: https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC