오늘 예제 코드 참고 사항
정렬의 방법에 대한 텍스트 설명이 난해하다. (내가 이해한 기준으로 작성해서..ㅠ)
설명을 참고로 예제 코드를 직접 실행해보고 테스트용 출력의 주석을 해제+실행해보면서 어떻게 정렬되어가는지 관찰해보며 이해하자.
정렬
데이터를 특정한 규칙(기준)에 맞게 순서대로 나열하는 것이다. (오름차순, 내림차순)
반복문을 이용해 요소끼리 비교하여 정렬한다. 따라서 정렬 알고리즘은 resource 소모가 크다. (메모리를 많이 사용한다.)
정렬의 목적
데이터를 정렬하면 데이터를 처리할 때 편리하다.
출력된 데이터의 가독성을 높일 수 있다 → 보기 좋게 검색할 수 있다.
정렬의 종류
선택 정렬, 버블 정렬, 삽입 정렬, 힙 정렬, 퀵 정렬, 쉘 정렬, ...
- 데이터의 규모나 형태에 따라 성능이 좋은 정렬이 다르다. (데이터에 맞는 정렬 방법을 사용해야 한다.)
향상된 for문 / for-each문
배열을 처음부터 끝까지 모든 요소를 참조할 때 간단하게 작성할 수 있다.
예제 코드를 보면 이해하기 쉽다. for-each(향상된 for문) 의 ( ) 안에 콜론(:) 왼쪽에는 배열의 요소 데이터타입과 사용할 변수명(새로 선언하는 변수명이다)을 써주고 콜론(:)의 오른쪽에는 참조할 배열명을 써주면 된다.
구조 형태
for (배열의요소의데이터타입 변수명 : 데이터배열명)
{
변수명을 이용한 코딩...
}
향상된 for문 / for-each문 예제 코드
int[] a = {52, 42, 12, 62, 60}; System.out.print("Source Data : "); for (int n : a) // int n은 for 문 안에서 사용할 변수 선언, a는 참조할 배열명 System.out.print(n + " "); //--==>> Source Data : 52 42 12 62 60
선택 정렬
첫번째~마지막-1 까지 자리(index)를 (선택)고정시키고 다른 값들과 순차적으로 비교하여 고정시킨 자리의 값을 결정한다(정렬한다).
※ 오름차순 기준 (1 2 3 ..)
1. 첫 번째 위치(index)를 선택하고 다음 값들과 순차적으로 비교한다(총 n-1회 비교). 비교할 때마다 상대값이 더 작은 경우 값을 바꾼다(swap). 마지막 값까지 비교하면 가장 작은 값이 정해진다.
2. 두 번째 위치 값을 선택하고 위 과정을 반복한다.(총 n-2회 비교)
3. 가장 오른쪽 위치(정렬 후 가장 큰 값이 올 자리)를 제외한 모든 index를 반복하면 가장 큰 값은 자동으로 자리잡는다.
4. 정렬이 반복할 때까지 위 과정을 반복하면 가장 작은 수부터 서서히 자리를 찾아간다.
/*================================= ■■■ 정렬(Sort) 알고리즘 ■■■ - 선택 정렬(Selection Sort) =================================*/ // 실행 예) // Source Data : 52 42 12 62 60 // Sorted Data : 12 42 52 60 62 // 계속하려면 아무 키나 누르세요... public class Test110 { public static void main(String[] args) { int[] a = {52, 42, 12, 62, 60}; int i,j; System.out.print("Source Data : "); for(int n : a) System.out.print(n + " "); System.out.println(); //--==>> Source Data : 52 42 12 62 60 // Selection Sort 구현 for (i=0; i<a.length-1; i++) { for (j=i+1; j<a.length; j++) { //if(a[i] < a[j]) // 내림차순 정렬 if(a[i] > a[j]) // 오름차순 정렬 { // 비트연산자로 swap a[i] = a[i]^a[j]; a[j] = a[j]^a[i]; a[i] = a[i]^a[j]; } } // 테스트 출력(변화 확인용) /* for (int n : a) System.out.print(n + " "); System.out.println(); */ } System.out.print("Sorted Data : "); for(int n : a) System.out.print(n + " "); System.out.println(); } } // 실행 결과 /* Source Data : 52 42 12 62 60 Sorted Data : 12 42 52 60 62 계속하려면 아무 키나 누르십시오 . . . */
버블 정렬
정렬기준(오름/내림)에 따라 오른쪽 옆자리와 크기를 비교하여 swap을 결정한다. 각 반복회전마다 가장 오른쪽의 값이 결정되는데, swap 해나가는 모습이 마치 비눗방울이 옆자리로 퍼져나가는 듯한 모습을 연상시켜서 버블정렬이라고 한다.
※ 오름차순 기준 (1 2 3 ..)
1. 첫 번째 반복 회전(1회전) 동안 0번째 index 부터 끝까지 순차적으로 오른쪽 자리 값과 비교한다(총 n-1회 비교). 오른쪽 index의 값이 왼쪽 값보다 작은경우 값을 바꾼다(swap). 마지막 값까지 비교하면 가장 큰 값이 가장 오른쪽까지 이동된 상태다. 가장 큰 값은 자리를 찾았으므로 다음 반복부터는 비교대상에서 제외한다.
2. 두 번째 반복 회전(2회전) 동안 0번째 index 부터 비교해야할 수까지 순차적으로 오른쪽 자리 값과 비교한다(총 n-2회 비교). 비교가 끝나면 비교한 수 중에서 가장 큰 값이(모든 값 중 두번째 큰 값) 자리잡는다.
3. 정렬이 완료될때까지 위 과정을 반복한다. 가장 큰값부터 서서히 자리를 찾아간다.
/*================================= ■■■ 정렬(Sort) 알고리즘 ■■■ - 버블 정렬(Bubble Sort, 거품 정렬) =================================*/ // 실행 예) // Source Data : 52 42 12 62 60 // Sorted Data : 12 42 52 60 62 // 계속하려면 아무 키나 누르세요... public class Test111 { public static void main(String[] args) { int[] a = {52, 42, 12, 62, 60}; int i,j; System.out.print("Source Data : "); for(int n : a) System.out.print(n + " "); System.out.println(); //--==>> Source Data : 52 42 12 62 60 // Bubble Sort 구현 for (i=1; i<a.length; i++) // 웅~~~~~~~~ →뒤에서 비교대상을 하나씩 줄여 { for (j=0; j<a.length-i; j++) { if (a[j] > a[j+1]) // 오름차순 정렬 { a[j] = a[j]^a[j+1]; a[j+1] = a[j+1]^a[j]; a[j] = a[j]^a[j+1]; } } // 테스트 출력(변화 확인용) /* for (int n : a) System.out.print(n + " "); System.out.println(); */ } System.out.print("Sorted Data : "); for(int n : a) System.out.print(n + " "); System.out.println(); } } // 실행 결과 /* Source Data : 52 42 12 62 60 Sorted Data : 12 42 52 60 62 계속하려면 아무 키나 누르십시오 . . . */
삽입 정렬
(0번째 자리를 건너뛰고) 1번째 index 값을 임시 저장소 temp에 저장하고 왼쪽 방향으로 정렬기준에 맞게 비교한다. swap이 일어날 때마다 임시저장한 비교값을 삽입하는 형태로 정렬한다. 기준 값은 오른쪽으로 이동한다.
삽입 정렬의 텍스트 설명은 특히 도움이 안될 것이다. 테스트 출력 주석을 해제하고 결과를 관찰하면서 나름의 해석을 붙이는 게 좋다.. (임시 저장소 temp는 삽입할 값을 저장해두는 용도!)
테스트 출력을 봐도 이해가 안될 수 있다. temp에 저장된 값과 원본데이터 그리고 변화한 형태를 잘 관찰해야한다.
/*================================= ■■■ 정렬(Sort) 알고리즘 ■■■ - 삽입 정렬(Insert Sort) =================================*/ // 실행 예) // Source Data : 52 42 12 62 60 // Sorted Data : 12 42 52 60 62 // 계속하려면 아무 키나 누르세요... public class Test112 { public static void main(String[] args) { int[] a = {52, 42, 12, 62, 60}; System.out.print("Source Data : "); for(int n : a) System.out.print(n + " "); System.out.println(); // Insert Sort 구현 for (int i=1; i<a.length; i++) { int temp = a[i]; int j = i-1; while (j>=0 && a[j]>temp) { a[j+1] = a[j]; j--; } a[j+1] = temp; // 테스트 출력 (변화 확인용) /* for (int n : a) System.out.print(n + " "); System.out.println("\ttemp : " + temp); */ } System.out.print("Sorted Data : "); for(int n : a) System.out.print(n + " "); System.out.println(); } } // 실행 결과 /* Source Data : 52 42 12 62 60 Sorted Data : 12 42 52 60 62 계속하려면 아무 키나 누르십시오 . . . */
향상된 버블 정렬
앞에서 확인해 본 Selection Sort(Test110) 나 Bubble Sort(Test111)의 성능은 같다. (→ 반복의 횟수로 추정)
하지만, 향상된 Bubble Sort 는 대상 데이터의 구조에 따라 불필요한 반복문을 수행하지 않으므로 일반 Bubble Sort 나 Selection Sort 보다 성능이 좋게 나타날 수 있다.
원본 데이터 : 61 15 20 22 30
15 20 22 30 61 - 1회전 (스왑 발생하면 flag = true) → 다음 회전 진행 ○
15 20 22 30 61 - 2회전 (스왑 발생하지 않았다면 flag = false) → 다음 회전 진행 Ⅹ
→ 위 원본 데이터로 1회전, 2회전 정렬을 해보니, 2회전에서 swap(자리바꿈)이 전혀 일어나지 않았기 때문에 정렬이 완료된 것으로 보고 불필요한 추가 연산(더 이상의 회전)은 무의미한 것으로 판단하여 추가적인 반복문을 수행하지 않는다.
/*================================= ■■■ 정렬(Sort) 알고리즘 ■■■ - 향상된 버블 정렬(Bubble Sort) =================================*/ // 실행 예) // Source Data : 10 50 22 31 43 // Sorted Data : 10 22 31 43 50 // 계속하려면 아무 키나 누르세요... public class Test113 { public static void main(String[] args) { int[] a = {10, 50, 22, 31, 43}; /* 10 50 22 31 43 == -- 10 50 22 31 43 == -- 10 22 50 31 43 // swap 발생 == -- 10 22 31 50 43 == -- 10 22 31 43 50 ----------------------------- 1회전 → swap 발생했으니 flag는 true 10 22 31 43 50 == -- 10 22 31 43 50 == -- 10 22 31 43 50 == -- ----------------------------- 2회전 → swap 발생하지 않음 → flag는 false flag가 false 이면 정렬 완료. */ System.out.print("Source Data : "); for(int n : a) System.out.print(n + " "); System.out.println(); // 향상된 Bubble Sort boolean flag; // do-while문의 조건식에서 활용된다. int pass = 0; // 정렬이 완료된 데이터 갯수 // for문의 조건식에서 활용된다. do { //-- 향상된 버블 정렬은 몇 회전으로 수행되는지 출력을 통해 확인하는 코드 //System.out.println("반복문 수행"); //-- 2번 출력된다.(총 2회전으로 정렬 완료) flag = false; //-- 자리바꿈이 발생할 경우 true 로 설정 pass++; for (int i=0; i<a.length-pass; i++) { if (a[i] > a[i+1]) { // 자리 바꾸기 a[i]=a[i]^a[i+1]; a[i+1]=a[i+1]^a[i]; a[i]=a[i]^a[i+1]; flag = true; //-- 단 한번이라도 스왑(자리바꿈)이 발생하게 되면 // flag 변수를 true 로 변경하여 // 다음 회전을 추가로 진행할 수 있도록 처리 } } } while (flag); //-- flag 변수가 false 라는 것은 // 회전이 부분적으로 발생하는 동안 swap이 일어나지 않은 경우로 // 더 이상의 반복문 수행은 무의미한 것으로 판단한다. System.out.print("Sorted Data : "); for(int n : a) System.out.print(n + " "); System.out.println(); } } // 실행 결과 /* Source Data : 10 50 22 31 43 Sorted Data : 10 22 31 43 50 계속하려면 아무 키나 누르십시오 . . . */
'자바 풀스택 과정 수업 정리 > 자바' 카테고리의 다른 글
| 자바 15-2 (2020.08.24) : 메소드 오버라이딩(@Override), final 메소드, 추상 클래스(Abstarct) (0) | 2020.09.02 |
|---|---|
| 자바 15-1 (2020.08.24) : 상속, super (0) | 2020.08.29 |
| 자바 13 (2020.08.20) : 메소드 오버로딩, 만년 달력, 주민번호 유효성 검사 (0) | 2020.08.24 |
| 자바 12-2 (2020.08.19) : 클래스 변수, 클래스 메소드, 인스턴스 변수, 인스턴스 메소드 (0) | 2020.08.24 |
| 자바 12-1 (2020.08.19) : 접근제어 지시자, 정보은닉, 캡슐화 (0) | 2020.08.23 |
최근댓글