기본정렬

이 글은 공부한 내용을 기반으로 정리하는 글이오니 건저한 비판은 언제든 환영합니다.

기본적으로 기본정렬은 선택정렬, 삽입정렬, 버블정렬 이렇게 3가지라고 생각합니다.

그렇다면 정렬은 무엇일까요?

정렬이란?

제가 생각하는 정렬이라고 생각하는 정의는 기준점을 잡고 차례대로 순서를 나열하는 것이라고 생각합니다.

예를 들면 오름차순으로 정렬한다는 것은, 숫자로 설명을 하면 1,2,3,4,5........ 식으로 낮은 숫자부터 높은 숫자로 나열하는 것 입니다.

이렇듯이 기준을 잡고 나열 하는 것을 정렬이라고 생각합니다.

 

선택정렬이란?

먼저 선택정렬에 대해서 설명을 하겠습니다. 선택정렬이라고 하는 것은 '|'앞은 정렬이 완료가 된 것 입니다.

이게 무슨 이야기냐면, 이제 설명 드리겠습니다.

저는 오름차순으로 숫자를 정렬을 할 것입니다. 먼저 숫자가 5개가 배열에 있습니다. (7, 5, 2, 1, 8)

이 숫자들을 오름차순으로 정렬을 한다면은 1,2,5,7,8으로 정렬이 될 것입니다.

그렇다면 선택 정렬 알고리즘으로 정렬을 한다면은

1st 1 7 5 2 8

2st 1 2 7 5 8

3st 1 2 5 7 8

4st 1 2 5 7 8

 

3번만에 정렬이 완료가 되었지만, 코드로 로직을 짠다면은 4번으로 완료가 되었습니다.

이제 코드로 보겠습니다.

 

import java.util.Scanner;
public class Main{
    public static void main(String[] args){

       // Please Enter Your Code Here
       Scanner sc = new Scanner(System.in);
       
       int[] array = new int[5];
       
       for(int i = 0 ; i<5; i++){
         array[i] = sc.nextInt();
       }
       
       for(int i = 0 ; i<5; i++){
         for(int j = i+1 ; j<5 ; j++){
           if(array[i]>array[j]){
             int temp = array[i];
             array[i] = array[j];
             array[j] = temp;
           }
         }
       }
       
       for(int i = 0 ; i<5 ; i++){
         System.out.println(array[i]);
       }

    }
}

코드 상으로 이렇게 됩니다.

하나하나 뜯어보도록 하겠습니다.

제가 뜯어볼 곳은 이중 for문으로 되어 있는 곳입니다.

7,5,2,1,8 이란 순서로 배열이 되어 있습니다.

 

    
       for(int i = 0 ; i<5; i++){
         for(int j = i+1 ; j<5 ; j++){
           if(array[i]>array[j]){
             int temp = array[i];
             array[i] = array[j];
             array[j] = temp;
           }
         }
       }

처음 부터 코드를 보면 0번째 배열에 들어가 있는 '7'부터 비교를 하겠습니다.

'7',5,2,1,8이라는 숫자가 있다면 먼저 7과 5를 비교를 하면 5가 작으니 순서가 변경이 됩니다.

5,7,2,1,8이라는 순서로 변경이 됩니다. 이제는 5라는 숫자가 비교 대상입니다.

그 이후에는 5와 2가 비교를 하게 됩니다. 또 다시 순서가 바뀌게 됩니다.
그래서 2,7,5,1,8이라는 숫자로 배열이 됩니다. 이제는 2라는 숫자가 비교 대상이 됩니다.

또 다시 2와 1을 비교를 한다면 1이 작기 대문에 

1,7,5,2,8로 배열이 됩니다. 1이 비교대상이기 때문에 1과 8을 비교하게 되면 1이 작기 때문에 바뀌지 않게 됩니다.

 

그래서 0번째 위치의 배열은 완료가 되기 때문에

1st 1 '|' 7 5 2 8 로 정렬이 되게 되었습니다. 아까 '|' 앞은 정렬이 완료가 되었다고 말씀을 드렸지요? 설명을 드렸듯이

1보다 작은 것은 없으니 0번째는 완료가 되었고 '|' 앞은 정렬이 완료가 되었습니다.

위에 로직과 마찬가지로 그 이후도 똑같은 로직으로 실행이 됩니다.

 

 

삽입 정렬이란?

선택 정렬에서 설명드린 '|' 앞은 완료가 되었다는 설명을 드릴 수 있습니다.

먼저 코드를 보여드리겠습니다.

import java.util.Scanner;

 

public class InsertSort {

 

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		int[] array = new int[10];

		Scanner sc = new Scanner(System.in);

		for(int i = 0 ; i<5 ; i++) {

			array[i] = sc.nextInt();

		}

		

		for(int i = 0 ; i<5 ; i++) {

			

			for(int j = i ; i>=1 ; j--) {

				if(array[j-1] > array[j]) {

					int temp = array[j-1];

					array[j-1] = array[j];

					array[j] = temp;

				}

				else break;

			}

		}

 

	}

 

}

이번에도 숫자를 7,5,2,1,8로 설명드리도록 하겠습니다.

		for(int i = 0 ; i<5 ; i++) {

			

			for(int j = i ; i>=1 ; j--) {

				if(array[j-1] > array[j]) {

					int temp = array[j-1];

					array[j-1] = array[j];

					array[j] = temp;

				}

				else break;

			}

		}

먼저 7,5,2,1,8순서 니까 7을 먼저 비교해야 하지만 안의 for문이 i가 1보다는 크고같아야 하니까 충족이 되지 않으니 다음 for문으로 넘어갑니다.  

그러니 일단 

1st 7'|',5,2,1,8 순서로 되겠습니다. 

그리고 그 이후로 가게 된다면 5의 차례입니다.

7과 5를 비교를 한다면 5가 작게 되니 순서를 변경하면 됩니다.

그러게 되면 

2st 5,7'|',2,1,8 순서로 정해지게 됩니다.

여기서 잠깐 선택 정렬과 '|' 개념이 다르게 느껴지지 않으세요?

'|'의 의미는 일부적으로 정렬이 완료가 되었다고 느껴지게 됩니다.

하지만 '|'의미가 선택정렬과 다르게 되서 왜 굳이 쓰는 건가 생각이 들지 않으신가요?

그것은 시간복잡도라는 개념이 들어가면 이해가 되지만 나중에 따로 시간복잡도에 대해서 글을 쓰도록 하겠습니다.

일단 그 이후로 진행하겠습니다. 이번에는 '2' 순입니다.

먼저 7와 비교를 하며 2가 작기때문에 2와 순서가 바뀌게 되고, 그 이후 5와 비교해도 작기 때문에 가장 앞으로 빠지게 되며

3st 2,5,7'|',1,8 순으로 됩니다.

그 다음인 1도 2와 똑같은 방식으로 가장 앞으로 가게 되므로

4st 1,2,5,7'|',8로 순서가 정해집니다.

가장 중요한 것은 여기서 입니다. 마지막은 8이지요? 8과 7을 비교하지만 7이 더 작으니, 8은 한 번만의 비교로 끝나게 됩니다.

어떻게 보면 상황에 따라서 선택정렬보다도 빠를 수가 있겠네요

최종적으로 

1,2,5,7,8'|'로 정렬이 됩니다.

 

버블정렬

마지막으로 버블정렬에 대해서 설명드리겠습니다.

버블정렬은 근접한 배열의 위치에 있는 원소들끼리 비교하는 정렬방법 입니다.

먼저 코드를 보여드리도록 하겠습니다.

import java.util.Scanner;
public class Main{
    public static void main(String[] args){

       // Please Enter Your Code Here
       
       Scanner sc = new Scanner(System.in);
      
       int[] array = new int[10];
        
       for(int i = 0 ; i<5 ; i++){
         array[i] = sc.nextInt();
       }
       
       for(int i = 0 ; i<5 ; i++){
         for(int j = 0 ; j<5-i-1 ; j++){
           if(array[j]>array[j+1]){
             int temp = array[j];
             array[j] = array[j+1];
             array[j+1] = temp;
           }
         }
       }
       
       for(int i = 0 ; i<5 ; i++){
         System.out.println(array[i]);
       }
       
    }
}

그리고 이제 설명을 해드리도록 하겠습니다.

버블 정렬을 하기 위해서 2개의 조건에 대해서 설명해 드리도록 하겠습니다.

첫 번째, 근접한 배열에 있는 원소들 끼리 비교한다. 

두 번째, '|'의 방향은 배열의 마지막에서 부터 0번째로 넘어온다.

 

먼저 첫 번째 부터 설명해 드리겠습니다.

5개의 배열에 각각 숫자가 있습니다. 그 숫자들은 4,8,5,1,9 입니다. 

가장 먼저 비교해야 하는 숫자는 4와 8입니다. 하지만 4가 작기 때문에 바뀌지가 않습니다.

그리고 다음 비교해야 할 대상은 8,5 입니다. 5가 작기 때문에 5와 8의 위치가 바뀌게 됩니다.

이제 8과 1을 비교해서 바뀌게 되며, 마지막으로 8과 9가 비교하지만 8이 작기 때문에 바뀌지 않습니다.

그래서 

1st 4,5,1,8, | '9' 가 되게 됩니다.

여기서 2 번째 '|'의 위치가 앞선 두개의 배열과 다르게 뒤에서 부터 시작을 하지요?

이건 '|'의 위치의 뒤는 정렬이 완료가 되었다는 뜻입니다.

이렇듯이 9가 들어있는 4번째 인덱스는 결정이 되었다는 뜻입니다.

그래서 

2st 4,1,5, | 8, 9 가 되며

3st 1,4, | 5, 8, 9 

4st 1, | 4, 5, 8 , 9 

5st | 1, 4,5,8,9 로 완료가 되었습니다.

 

이렇듯이 제가 생각하는 그리고 배열을 정렬을 가장 쉽게 정렬할 수 있는 방법인

3가지를 설명하였습니다.

개인적으로 이 3가지 배열을 그렇게 사용할 일은 그리 많지 않을겁니다.

왜냐하면 시간복잡도에서 더 빠른 정렬방법이 있습니다.

하지만 이런 것도 있구나 하면서 읽어주시면 감사하겠습니다.