[Algorithm] Sorting Algorithm/정렬 알고리즘이란?(버블정렬, 선택정렬, 삽입정렬)

정렬(sort)알고리즘이란 ?

두개 이상의 데이터를 비교해 원하는 순서대로 정렬하는 알고리즘이다.(오름차순, 내림차순)

주로 불규칙한 데이터들을 정렬한 다음 탐색해야하는 경우에 정렬 알고리즘을 사용한다.

정렬알고리즘의 종류는 매우 다양하다.  버블, 삽입, 선택, 힙, 퀵, 기수 등.

그 중 버블정렬, 삽입정렬, 선택정렬에 대해 기록할 것이다.

 

 

1. 선택정렬

선택정렬은 주어진 데이터들 중 현재위치(0번방)에 맞는 데이터(가장작은수)를 찾아 데이터간의 위치를 swap하는 방식이다. (가장작은 수를 찾아와서 앞에둔다. 반복)

 

오름차순을 예시로 들 경우,

1) 모든 데이터들 중 0번째방에 들어올 가장 작은 데이터를 찾는다. 

2) 0번째방에 들어있던 데이터와 가장작은 데이터를 교환한다.

3) 1번째방에 들어올 두번째로 작은 데이터를 찾는다.

4) 1번째 방에 들어있던 데이터와 두번째로 작은 데이터를 교환한다.

5) ..반복..

 

데이터들의 기존정렬순서와 상관없이 무조건 전체데이터를 검사하기 때문에, 시간복잡도는 한결같이 O(n^2) 이다.

 

import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int num=in.nextInt();
		int arr[]=new int[num];
		for(int i=0;i<num;i++) arr[i]=in.nextInt();

		for(int i=0;i<num-1;i++){
			int idx=i;
			for(int j=i+1;j<num;j++){
				if(arr[j]<arr[idx]) idx=j;
			}
			int tmp = arr[i];
			arr[i] = arr[idx];
			arr[idx] = tmp;
		}
		for(int a:arr)
		System.out.print(a+" ");
	}
}

결과

 

 

2. 버블정렬

옆에있는 데이터와 비교하여 값을 교환하는 방식이다. (큰값을 뒤로보낸다.)

 

오름차순을 예로들면,

1) 0번방 데이터 vs 1번방 데이터 

2) 0번방데이터가 1번방데이터보다 크면 swap, 작으면 그대로.

3) 1번방 데이터 vs 2번방데이터

4) 1번방데이터다 2번방데이터보다 크면 swap, 작으면 그대로.

5) 반복

 

//코드는 버블정렬이 제일 간단하다. 하지만 다른 포스트에서 최악의 성능이라며, 절대 쓰지 않는 정렬이라고했다. ㅋ참내~ 아마 이중for문 안에서 끊임없이 데이터를 변경해야하기 때문일것이다. 하지만, 한번만 돌아도 되기 때문에 이미 정렬되어있는 데이터에서는 가장 효율적이라고한다.

 

시간복잡도는 O(n^2)

import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int num=in.nextInt();
		int arr[]=new int[num];
		for(int i=0;i<num;i++) arr[i]=in.nextInt();

		for(int i=0;i<num;i++){
			for(int j=0;j<num-1-i;j++){
				if(arr[j]>arr[j+1]){
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		for(int a:arr)
		System.out.print(a+" ");
	}
}

결과

 

3. 삽입정렬

삽입정렬은 기준데이터보다 앞에있는 데이터들과 비교하며 순서에 맞는 데이터를 삽입한다.

(나(i) 보다 작은수가 나올 때까지 큰수를 뒤로 보낸다. 그러다 작은수가 나오면 작은수 다음에 나를 넣는다. )

 

오름차순을 예로들면

 (외부 for문이 i=1일때)

1) 1번방데이터 vs 0번방데이터

2) if ( 1번방데이터 < 0번방데이터) 

3) 0번방 데이터는 1번방 데이터보다 크기 때문에 뒤로보낸다. (1번방에 0번방데이터를 넣는다.)

 

 (외부 for문이 i=2일때)

4) 2번방데이터 vs 1번방데이터 

5) if ( 2번방데이터 < 1번방데이터)

6) 1번방데이터는 2번방데이터 보다 크기 때문에 뒤로보낸다.

7) 2번방데이터 vs 0번방데이터

8) if ( 2번방데이터 > 0번방데이터)

9) 0번방데이터가 2번방데이터 보다 작으면 1번방에 2번방데이터 삽입한다.

 

//세가지 정렬방법중 가장 복잡하다.

먼저 외부 for문의 i방데이터(이하 idx)를 기준으로 둔다.

내부 for문의 j가 0이되거나, idx보다 더 큰 i-n방데이터를 만날 때까지,

i-n방 데이터와 idx를 비교하며 i-n방의 데이터를 뒤로보낸다.

 

시간복잡도는 O(n^2)

import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int num=in.nextInt();
		int arr[]=new int[num];
		for(int i=0;i<num;i++) arr[i]=in.nextInt();

		for(int i=1;i<num;i++){  //i시작값은 1부터. why? i보다 앞에있는 데이터와 비교하며 삽입해야하니까.
			int idx=arr[i],j;    //내부for문의 j를 미리 선언해준다. why? 내부for문이 끝난 다음, j+1한 위치에 idx를 삽입해줘야하기 때문이다.
			for(j=i-1;j>-1;j--){ //내부for문은 i-1에서 시작하고, 계속 작아진다. i랑 i보다 앞에 있는 데이터들을 비교하며 데이터를 삽입해주기 때문.
				if(arr[j]>idx) arr[j+1] = arr[j];
				else break;
			}
			arr[j+1]=idx; // j를 미리 선언해둔 이유. 내부for문이 종료된 j에서 +1한 위치에 idx를 삽입해준다.
		}
		for(int a:arr)
		System.out.print(a+" ");
	}
}

결과