정렬 기본 예제 소스 O(N^2)

알고리즘 정렬기법 중 가장 기본적인 정렬 삽입, 버블, 선택 정렬을 정리했다

시간복잡도는 O(N^2)이고, 익숙해질 때까지 소스를 보면서 눈에 익히고 구현에 대해서도 계속 생각해보자.

선택정렬이 제일 헷갈렸다... 처음엔 제일 쉬워보였는데 어렵네

 

삽입정렬

import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 1; i < n; i++) {
            tmp = a[i];
            for(j = i - 1; j >= 0 && a[j] > tmp; j--) {
                a[j+1] = a[j];
            }
            a[j+1] = tmp;
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}

 

버블정렬

import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            for(j = 0; j < n-i-1; j++) {
                if(a[j] > a[j+1]) {
                    tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
        
    }
}

 

선택정렬

import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp = 0;
        int j;
        int index;
        
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            index = i;
            for(j = i + 1; j < n; j++) {
                if(a[j] < a[i]) {
                    index = j;
                    tmp = a[i];
                    a[i] = a[index];
                    a[index] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}