✅ 버블정렬

버블정렬(Bubble Sort) : 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. (맨 오른쪽부터 최대값을 채워넣어 점점 줄인다)

동작과정

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

구현코드 ( Java)

void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length; i++) {       
		for(int j= 1 ; j < arr.length-i; j++) { 
			if(arr[j-1] > arr[j]) {             
                // swap(arr[j-1], arr[j])
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}

• 시간복잡도 : 최선,평균,최악의 경우 모두 O(N^2)이다.
• 공간복잡도 : O(N)
• 장점 : 구현이 매우 간단하고, 코드가 직관적, 안정정렬이다.
• 단점 : 시간복잡도 측면에서 굉장히 비효율적

✅ 선택정렬

선택정렬(Selection Sort) : 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.
(맨 왼쪽부터 최솟값을 채워넣어 점점 줄인다)

동작과정

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다. (pass)
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

구현코드 ( Java)

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;
            }
        }
         swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

• 시간복잡도 : 최선,평균,최악의 경우 모두 O(N^2)이다.
• 공간복잡도 : O(N)
• 장점 : 단순하다. 버블정렬에 비해 비교적으로 효율적이다, 제자리 정렬
• 단점 : 시간복잡도 측면에서 버블정렬과 마찬가지로 굉장히 비효율적, 불안정정렬

✅ 삽입정렬

삽입정렬(Insertion Sort) : 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

동작과정

1. 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

구현코드 ( Java)

void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {   
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                          
   }
   System.out.println(Arrays.toString(arr));
}

• 시간복잡도 : 평균,최악의 경우 모두 O(N^2)이다. 그러나, 최선의 경우 O(N)이다.
• 공간복잡도 : O(N)
• 장점 : 단순하다. 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적임, 제자리 정렬, 안정정렬, 이전의 두 알고리즘에 비교하여 상대적으로 빠르다
• 단점 : 평균과 최악의 시간복잡도가 O(N^2)으로 비효율적, 이전의 두 알고리즘과 마찬가지로, 배열의 길이가 길어질수록 비효율적임.

참고 : https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html