JAVA 알고리즘 :: 정렬(1)

📝 정렬

• O(n²): 중첩 반복문 사용 ⇝ 비효율적
  • 버블 정렬
  • 선택 정렬
  • 삽입 정렬
• O(n logn)
  • 퀵 정렬
  • 병합 정렬
  • 힙 정렬

💡 버블 정렬

• 서로 근접한 요소끼리 자리 바꾸는 방식
• 비효율적
• 구현 코드

for (int i = 0; i < length; i++) {    
    for (int j = 0; j < length - i; j++) {  
        if (j + 1 < length && arr[j] > arr[j + 1]) {    
        	// 인접한 애들끼리 비교하면서 자리 교체
            arr[j] = arr[j] + arr[j + 1];
            arr[j + 1] = arr[j] - arr[j + 1];
            arr[j] = arr[j] - arr[j + 1];
        }
    }
}

💡 선택 정렬

• 해당 자리에 들어갈 최소값 또는 최대값(역순 정렬 시) 찾는 방식
• 비효율적
• 구현 코드

for (int i = 0; i < length; i++) {
    int min = i;

    for (int j = i + 1; j < length; j++) {
        if (arr[j] < arr[min]) 
            min = j;
    }
    
    // 나보다 작은게 있으면 치환
    if (min != i) {
        arr[min] = arr[min] + arr[i];
        arr[i] = arr[min] - arr[i];
        arr[min] = arr[min] - arr[i];
    }
}

💡 삽입 정렬

• 두번째 인덱스부터 시작해서 자신의 앞에있는 값들과 비교하여 적절한 위치를 찾아 넣어주는 방식
• 최소 시간복잡도: O(n)
• 정렬이 어느정도 되있는 경우에 최소한의 비교와 연산이 이루어지므로, 성능이 좋아 사용
• 구현 코드

for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int position = i;
    
    // 자신의 바로 앞에 노드보다 값이 크기 전까지 뒤로 한칸씩 넣어줌 
    while (position > 0 && key < arr[position - 1]) {
        arr[position] = arr[position - 1];
        position--;
    }

    arr[position] = key;
}