[코테] 간단하게 정리된 코테 - 정렬

정렬 정의

1. 버블 정렬

• 정렬 방법 : 인접한 노드끼리 비교하여 왼쪽 인덱스의 값이 크다면 자리 변경하며, 오른쪽 부터 큰값 정렬
• 외부 반복 : [Index 0] ~ [Index (배열 크기 -1)] 까지 반복
• 내부 반복 : [Index 0] ~ [Index (배열 크기 -1 - 외부 Index)] 까지 반복
• 정렬 한턴 종료 조건 : 반복문 완료시 종료
• 정렬 완료 조건 : 자리 변경이 없을시 종료

• 코드 (for 문이 2개 이므로 시간 복잡도 O(n*n))

import java.util.Collections;
public ArrayList<Integer> bubble_sort(ArrayList<Integer> data){
    for(int i = 0 ;i < data.size(); i++){
        boolean isSwap = false;
        for(int j = 0 ;j < data.size() - 1 - i ; j++){
            if(data.get(j) > data.get(j+1)){
                Collections.swap(data, j, j+1);
                isSwap = true;
            }
        }
        if(!isSwap){
            break;
        }
    }
    return data;
}
ArrayList<Integer> data = new ArrayList<>();
data.add(7);
data.add(5);
data.add(4);
data.add(3);
data.add(1);
bubble_sort(data);
System.out.println(data);
// [1, 3, 4, 5, 7]

2. 선택 정렬

• 정렬 방법 : 선택한 자리에 최솟값 으로 자리 변경하며, 왼쪽 부터 최솟값 정렬
• 외부 반복 : [Index 0] ~ [Index (배열 크기 -2)] 까지 반복
• 내부 반복 : [Select Index + 1] ~ [Index (배열 크기 -1)] 까지 반복
• 정렬 한턴 종료 조건 : 반복문 완료시 종료
• 정렬 완료 조건 : 반복문 완료시 종료

• 코드 (for 문이 2개 이므로 시간 복잡도 O(n*n))

import java.util.Collections;
public ArrayList<Integer> select_sort(ArrayList<Integer> data){
    for(int i = 0; i < data.size()-1; i++){
        int least = i;
        for(int j = i+1; j < data.size() ; j++){
            if(data.get(j) < data.get(least)){
                least = j;
            }
        }
        
        if(least != i){
            Collections.swap(data,i,least);
        }
    }
    return data;
}
ArrayList<Integer> data = new ArrayList<>();
data.add(7);
data.add(5);
data.add(4);
data.add(3);
data.add(1);
select_sort(data);
System.out.println(data);
// [1, 3, 4, 5, 7]

3. 삽입 정렬

• 정렬 방법 : 두번째 자리(Index [1])부터 Key 값으로 지정후, Key 값 보다 앞자리 중 순서가 맞는 자리에 Key 값 삽입하여 정렬
• 외부 반복 : [Key Index] ~ [Index (배열 크기 -1)] 까지 반복
• 내부 반복 : [Key Index -1] ~ [Index 0] 까지 반복
• 정렬 한턴 종료 조건 : Key 가 앞자리 수보다 크다면 종료
• 정렬 완료 조건 : 반복문 완료시 종료

• 코드 (for 문이 2개 이므로 시간 복잡도 O(n*n))

public ArrayList<Integer> insert_sort(ArrayList<Integer> data){
    for(int i = 1; i < data.size(); i++){
        for(int j = i;j > 0;j--){
            if(data.get(j) < data.get(j-1)){
                Collections.swap(data,j,j-1);
            }else{
                break;
            }
        }
    }
    return data;
}

ArrayList<Integer> data = new ArrayList<>();
data.add(7);
data.add(5);
data.add(4);
data.add(3);
data.add(1);
insert_sort(data);
System.out.println(data);
// [1, 3, 4, 5, 7]

:: https://github.com/works-code/cote/tree/main/sort

GitHub - works-code/cote: 코딩 테스트 모음집