정렬을 하는 원시적인 방법 3가지 (Bubble, Selection, Insertion)

대표적인 기초! 정렬방법을 알아보고 구현을 해보자!

정렬이란 뭘까요오?

일단 쉽게 말하자면 5,2,3,1,4 가 있다고 가정하면 이 숫자를 오름차순 혹은 내림차순으로 정리한 것도 정렬이라고 할수 있죠???

이와 같이 숫자와 같은 데이터가 있을때 그걸 12345…. 혹은 987654… 이렇게 정리해도 정렬!

혹은 문자열이 있을때, a. , b~~ ,c~~~ 이렇게 사전처럼 앞글자를 기준으로 오름차순 내림차순 하는것도 정렬!!

(솔직히 이게 이해가 안가면 개발자를 떠나서 디지게 맞아야함) ^^;

---

자 그렇다면 자바에서는 정렬을 언제 쓰고 왜 쓸까요??

예를 들어 저희가 배열에 고객의 개인정보를 숫자에 넣어서 1~100 까지 무작위로 정리를 해놨다고 칩시다.

그러면 일단 배열은 직접 인덱스 번호를 쳐서 데이터를 열어보기 까지는 뭐가 들었는지 모르죠??…

그렇다면 1~100까지 하나씩 다 까가지고 일일히 확인을 해야되는데 컴퓨터도 이처럼 일일히 확인을 하게되면

작업처리 속도가 느려지겠죠…!

 

 

그래서 이진검색이라는 알고리즘을 사용하기 위해 데이터를 정렬하는 경우가 많습니다!!!

이진검색은 무조건 정렬된 데이터에서만 사용이 가능하기 때문이죠!

이진검색, 그리고 위에서 얘기한 일일히 다 검사하는 선형검색은 속도차이가 데이터에 따라서 몇십배 차이가 날 수도 있기에

왠만하면,,, 데이터를 정렬하는게 좀 걸리더라도 정렬을 한번 해놓으면, 검색은 무지하게 빠르니 정렬하는게 좋을겁니다!!!

자자 그래서 이제부터 가장 기초적이고, 원시적인 정렬알고리즘 3가지를 구현해볼게요!!

---

• Bubble sort (버블 정렬) 또 앞에 원소와 자신을 비교하여 계속 진행하게 됩니다.이걸 배열에 있는 원소만큼 (최대 n 만큼) 반복하게 되면 정렬이 끝나는겁니다!!
• ex) 1 , 4 ,2 ,6, 3 ⇒ 1, 2, 4, 3, 6 ⇒ 1, 2, 3, 4, 6 끗.
• 그렇게 되면 제일 작은 원소가 맨 앞에 도착하거나, 순서에따라 제일 큰 원소가 제일 끝에 도착해있겠죠??
• 버블정렬이란 맨 처음, 혹은 맨끝부터 바로 앞에 원소와 자기자신을 비교해서 크다면 서로 데이터를 맞바꾸고

Bubble sort 구현

for(int i=0; i<nums.length-1; i++) {
				for(int j=0; j<nums.length; j++ ) {
					if(nums[j+1]>nums[j]) {
						swap(nums, j+1, j);  // 밑에 swap하는 메소드.
					}
				}
				System.out.print(i+1+"회 정렬==>");
				display();  // 출력하는 메소드를 만들어놨습니다 미리.
				System.out.println();  // 줄바꿈
			}
		}

		private void swap(int[] arr, int i, int j) {
			int temp = a[i];
			a[i]=a[j];
			a[j]=temp;

---

• selection sort (선택정렬)오름차순으로 정렬한다고 가정을 하면,다시 위와 같은 방식으로 반복합니다!

 

Selection Sort 구현

private static void selection(int[] arr) {
		for(int i=0; i<arr.length-1; i++) {.    
			for(int j=i+1; j<arr.length; j++) {
				
					if(arr[j]<arr[i]) {
						int temp=arr[i];
						arr[i]=arr[j];
						arr[j]=temp;
						j--;
				}
			}

 

전체적인 코드의 흐름은 똑같습니다만,,,

위에 코드를 잠시 풀이해보자면 i=0번지이고 j는 항상 i+1 인덱스부터 ++하여 끝가지 탐색을합니다.

탐색과정에서 i인덱스 값보다 작은 j인덱스가 나오면 서로 교환을 하는것입니다!

 

 

• ---

  • Insertion Sort (삽입 정렬)
  삽입정렬은 최고의 케이스라면 O(logn)의 시간복잡도가 발생합니다.그래도 그중에서는 제일 킹왕짱~! 빠른 친구니까 한번 알아봅시다 😟본인 인덱스를 기준으로 그 밑에있는 모든 요소와 비교를 하여 교환을 합니다.삽입함으로써 정렬을 완성시킵니다! (코드를 보면 이해하기 쉬울겁니다 🙂)

  ---

  private static void Insertion(int[]arr) {
  			for(int i=1; i<arr.length; i++) {. // index 1부터 탐색합니다 (본인보다 작은 인덱스와 비교)
  			int j=i-1;  // j 는 i인덱스 번호보다 1작은 0부터 시작합니다.
  			int target=arr[i];   // 타겟 데이터 설정.
  			
  			while(j>=0 && target < arr[j]) {    // j가 0보다 작거나 target이 j인덱스보다 작을때까지 계속 반복합니다.
  				arr[j+1]=arr[j];     // 한칸씩 뒤로 미뤄줍니다.
  				j--;
  			}
  			// 위의 반복문에서 탈출했다는건 앞의 데이터가 타겟보다는 작다는 의미이므로
  			// 타겟 원소는 j번째 원소 뒤에 와야합니다.
  			arr[j+1]=target;      
  		}
  	}
  

• Insertion Sort 삽입정렬 구현
  • 한마디로 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아
  • 일단 삽입정렬은 인덱스 1번지 부터 시작합니다.
  • 물론 평균적으로 보면 버블정렬과 선택정렬의 시간복잡도와 동일합니다 ㅎㅎ….
  • 위에 코드를 잠시 풀이해보자면 i=0번지이고 j는 항상 i+1 인덱스부터 ++하여 끝가지 탐색을합니다.
  • Selection Sort 구현
  • 배열에서 최솟값을 찾고, 맨 앞자리의 숫자와 교환을 한 다음에 맨 앞자리를 제외한 나머지 값들중 최솟값을 찾고
  • 선택정렬은 제일 작은 숫자 or 큰 숫자 를 맨앞에 차례대로 정렬 시키는것을 의미합니다.

선택정렬은 제일 작은 숫자 or 큰 숫자 를 맨앞에 차례대로 정렬 시키는것을 의미합니다.

오름차순으로 정렬한다고 가정을 하면,

배열에서 최솟값을 찾고, 맨 앞자리의 숫자와 교환을 한 다음에 맨 앞자리를 제외한 나머지 값들중 최솟값을 찾고

다시 위와 같은 방식으로 반복합니다

선택정렬은 제일 작은 숫자 or 큰 숫자 를 맨앞에 차례대로 정렬 시키는것을 의미합니다.

오름차순으로 정렬한다고 가정을 하면,

배열에서 최솟값을 찾고, 맨 앞자리의 숫자와 교환을 한 다음에 맨 앞자리를 제외한 나머지 값들중 최솟값을 찾고

다시 위와 같은 방식으로 반복합니다!