심플하고 차분하게

▶ 들어가기 전에..

1. 컬렉션 프레임웍(Collection Framework)의 이해

https://www.youtube.com/watch?v=z9GpUGoYCw4

■ 용어 

▶ 컬렉션 (모아놨다)

▶ 프레임웍(정형화된 틀) : 라이브러리 + 프로그래밍 방식

    *라이브러리 : 다른 사람이 이미 만들어 놓은 걸 모아논 곳(라이브러리=도서관). 기능만 제공한다(ex. JavaAPI)

▶ 컬렉션 프레임웍 : 다수의 객체를 다루기 위한 표준화된 프로그래밍 방식 

    *객체 = 데이터 

    - java.util 패키지에 포함. (JDK2.0부터)

▶ 컬렉션 클래스

■ 컬렉션 프레임웍의 핵심 인터페이스

2. Collection인터페이스의 메소드

https://www.youtube.com/watch?v=RscGmop2Bzo 

■ Collection 인터페이스 _ 검색/추가/삭제/기타

■ List 인터페이스(순서O/중복O) _ 검색/추가/삭제/읽기/변경/추출/정렬

■ Set 인터페이스(순서X/중복X)_메소드는 컬렉션과 동일+집합 관련 메소드

- addAll(Collection c) : boolean [합집합]

- containsAll(Collection c) : boolean [부분집합]

- removeAll() [차집합]

- retainAll() [교집합]

■ Map 인터페이스(순서X/중복-키X,값O)

1. 알고리즘이란?

https://why-dev.tistory.com/6?category=917883 

2. 정렬

- 정의 : 이름,학번,키 등 핵심항목(key)의 대소관계에 따라 순서대로 값을 나열하는 것

- 안정성 : 키값이 같은 요소의 순서가 정렬 후에도 유지되는 것

   (ex. 같은 점수를 지닌 두 학생에 대해 학번으로 순번을 지정)

- 내부 정렬과 외부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 내부 정렬을 사용한다. 

- 정렬의 속도 비교 : 

https://youtu.be/ZZuD6iUe3Pc

3. 버블정렬, 선택정렬, 삽입정렬

1) 버블정렬 

원리 ) 안쪽에서 두개의 값을 비교한다 
       --> 한 줄 비교가 다 끝나면 마지막 값이 가장 큰 값(또는 가장 작은 값)
       --> 안 쪽은 n-1-i 만큼 두개씩 비교 & swap하면 된다.
       바깥쪽에서 이 과정을 n-1만큼 반복한다.

[코드]

package _02_정렬;

import java.util.Arrays;

public class _04_BubbleSort {

	public static void main(String[] args) {
		
		int[] arr = new int[10];
		
		random(arr);
		
		System.out.println(Arrays.toString(arr));
		
		//오름차순 버블 정렬을 구현하라
		int tmp;
		for (int i = 0; i < arr.length-1; i++) {
			for (int j = 0; j < arr.length-1-i; j++) {
				if (arr[j] > arr[j+1]) {
					tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		System.out.println(Arrays.toString(arr));
		
		//내림차순 버블 정렬을 구현하라
		for (int i = 0; i < arr.length-1; i++) {
			for (int j = 0; j < arr.length-1-i; j++) {
				if (arr[j] < arr[j+1]) {
					tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		System.out.println(Arrays.toString(arr));

	}
	
	public static int[] random(int[] arr) {
		
		OUTER :
		for (int i = 0; i < arr.length; i++) {
			
			arr[i] = (int)(Math.random()*10)+1;
			
			for (int j = 0; j < i; j++) {
				
				if (arr[j] == arr[i]) {
					i--;
					continue OUTER;
				}
			}
		}
		
		return arr;
		
	}

}

>> 결과

[10, 3, 8, 9, 4, 1, 7, 5, 2, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

2) 선택정렬 

원리 ) i index를 min(or max)으로 지정하고, 나머지 값들을 하나씩 비교한 뒤, 교환한다.

[코드]

package _02_정렬;

import java.util.Arrays;

public class _05_SelectionSort {

	public static void main(String[] args) {

		int[] arr = new int[10];
		
		random(arr);
		
		System.out.println(Arrays.toString(arr));
		
		//오름차순 선택정렬을 구현하라
		int min, tmp;
		for (int i = 0; i < arr.length-1; i++) {
			min = i; // 하나의 요소를 min으로 선택(이 값보다 작은 값을 찾는다)
			for (int j = i+1; j < arr.length; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			//i위치값과 min값을 swap
			tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;
		}
		System.out.println(Arrays.toString(arr));
		
		//내림차순 선택정렬을 구현하라
		int max;
		for (int i = 0; i < arr.length-1; i++) {
			max = i;
			for (int j = i+1; j < arr.length; j++) {
				if (arr[j] > arr[max]) {
					max = j;
				}
			}
			//i위치값과 max값을 swap
			tmp = arr[i];
			arr[i] = arr[max];
			arr[max] = tmp;
		}
		System.out.println(Arrays.toString(arr));

	}
	
	public static int[] random(int[] arr) {
		
		OUTER :
		for (int i = 0; i < arr.length; i++) {
			
			arr[i] = (int)(Math.random()*10)+1;
			
			for (int j = 0; j < i; j++) {
				
				if (arr[j] == arr[i]) {
					i--;
					continue OUTER;
				}
			}
		}
		
		return arr;
		
	}

}

>> 결과

[2, 9, 8, 5, 10, 1, 6, 4, 3, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

3) 삽입 정렬 (Insertion Sort)

- 거의 다 정렬된 상태의 데이터를 다시 정렬할 때, 가장 효과적인 알고리즘 (위 정렬 속도 비교 확인)

- 원리 : 아직 정렬되지 않은 부분의 첫번째 요소를 정렬한 부분의 알맞은 위치에 삽입한다.

- 장점 : 정렬이 되었거나 또는 그 상태에 가까우면 정렬 속도가 아주 빠름

- 단점 : 삽입할 곳이 멀리 떨어지면 이동(대입)하는 횟수가 많다

   (ex. 0~10까지 중 0제외 나머지는 정렬된 상태이나, 0값이 인덱스의 끝에 위치)

[코드]

package _02_정렬;

import java.util.Arrays;

public class _02_InsertionSort {

	public static void main(String[] args) {
		int[] arr = new int[10];
		
		random(arr);
		
		System.out.println(Arrays.toString(arr));
		
		//오름차순 삽입정렬을 구현하라
		int tmp;
		for (int i = 1; i < arr.length; i++) {
			tmp = arr[i];
			int j;
			
			for (j = i; j > 0 && arr[j-1] > tmp; j--) {
				arr[j] = arr[j-1];
			}
			arr[j] = tmp;	
		}
		System.out.println(Arrays.toString(arr));
		
		//내림차순 삽입정렬을 구현하라
		for (int i = 1; i < arr.length; i++) {
			tmp = arr[i];
			int j;
			for (j = i; j > 0 && arr[j-1] < tmp; j--) {
				arr[j] = arr[j-1];
			}
			arr[j] = tmp;
		}
		System.out.println(Arrays.toString(arr));
	}
	
	public static int[] random(int[] arr) {
		
		OUTER :
		for (int i = 0; i < arr.length; i++) {
			
			arr[i] = (int)(Math.random()*10)+1;
			
			for (int j = 0; j < i; j++) {
				
				if (arr[j] == arr[i]) {
					i--;
					continue OUTER;
				}
			}
		}
		
		return arr;
		
	}

}

>> 결과

[3, 1, 6, 4, 10, 2, 5, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

4. 셸 정렬 (Shell Sort)

[ 출처 ]

- 자바의 정석, 남궁성

- Do it! 자료구조와 함께 배우는 알고리즘 입문 [자바편], bogyoh shibata지음

- 기타 : 유투브