정렬

최소값 찾기

• 정렬 알고리즘을 이용하여 자료 정렬하기
• 원하는 순서에 있는 원소 가져오기

주어진 배열에서 최소값을 찾는 함수

FindMin(A):
	min ← A[0]//첫번째 원소가 최소라고 가정
	minIdx ← 0
	
	for (i ← 1; i < A.length; i++){
		if(min > A[i]){
			min ← A[i]
			minIdx ← i
		}
	}
    =======================================================================
    package test01;

public class FindMin {
	public static void main(String[] args) {
		int[] A = {32, 2, 33, 56, 2, 1, 4};
		
		int min = A[0];
		int minIdx = 0;
		
		for(int i=1; i< A.length; i++) {
			if(min > A[i]) {
				min = A[i];
				minIdx = i;
			}
		}
		System.out.println(min);
		System.out.println(minIdx);
	}
}

 선택정렬

주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식

SelectionSort(A)
	A:주어진 배열
	n:A.length, 배열 A의 원소의 개수
	
	//패스의 반복
	for i from 0 to n-2
		minIdx=i//매 패스마다 첫번째 원소를 최소값으로 가정
	 	for j from i+1 to n-1
	 		if A[j]<A[minIdx] then
	 			minIdx=j
	 			
	 			swap(A[minIdx], A[i])
===============================================================================
package test02;

import java.util.Arrays;

public class test2선택정렬 {
	public static void main(String[] args) {
		int[] A= {5,4,3,2,1};
		int n=A.length;
		
		//패스는 n-1회 반복
		for (int i = 0; i < n-1; i++) {
			//매 패스에서 첫번째 원소를 최소값이라 가정
			int minIdx=i;
			//그 다음 원소부터 마지막 원소까지 비교해나감.
			for (int j = i+1; j < n; j++) {
				if (A[j]<A[minIdx]) {
					minIdx=j;
				}
			}
			//swap
			int temp=A[minIdx];
			A[minIdx]=A[i];
			A[i]=temp;
			System.out.printf("%d번째 패스: %s\n", i+1, Arrays.toString(A));
		}
		System.out.println("최종 정렬 : "+Arrays.toString(A));
	}
}
//
1번째 패스: [1, 4, 3, 2, 5]
2번째 패스: [1, 2, 3, 4, 5]
3번째 패스: [1, 2, 3, 4, 5]
4번째 패스: [1, 2, 3, 4, 5]
최종 정렬 : [1, 2, 3, 4, 5]

순차검색

일렬로 되어 있는 자료를 순서대로 검색하는 방법

-정렬되지 않은 배열

// 정렬되지 않은 배열에서
// 찾고자 하는 값의 index를 찾아 반환한다.
// 못찾은 경우 -1을 반환한다.

sequentialSearch(A, key)
	A ← 주어진 배열
	n ← 주어진 배열의 크기
	key ← 찾고자 하는 값
	
	i ← 0
	while(i < n and A[i] != key)
		i ← i+1
	
	if(i<n) return i //A[i]가 key인 경우
	else return -1 //i>=n여서 못 찾은 경우
=========================================================================

public class test3순차검색_정렬안된경우 {
	public static void main(String[] args) {
		int[] A= {4,9,11,23,2,19,7};
		int idx=sequentialSearch(A, 2);
		System.out.println(idx);
		
		idx=sequentialSearch(A, 20);
		System.out.println(idx);
	}
	
	public static int sequentialSearch(int[] A, int key) {
		int n=A.length;
		
		int i=0;
		while(i<n&&A[i]!=key) {
			i++;
		}
		
		//while문을 빠져나오면
		//1. A[i]==key 인경우:찾은 경우
		//2. i>=n인 경우: 못 찾은 경우
		
		if (i<n) return i; //값을 찾은 경우
		else return -1;	 //값을 못 찾아 배열을 벗어난 경우
		
	}
}
//
4
-1

-정렬된 배열

// 정렬된 배열에서
// 찾고자 하는 값의 index를 찾아 반환한다.
// 못찾은 경우 -1을 반환한다.

sequentialSearch(A, key)
	A ← 주어진 배열
	n ← 주어진 배열의 크기
	key ← 찾고자 하는 값
	
	i ← 0
	while(A[i] < key)
		i ← i+1
	//종료되는 시점
	//1. 더 이상 볼 필요 없을 때 : A[i]>key
	//2. 찾았을 때 : A[i]==key
	
	//언제 반복?
	A[i]<key
	
	if(A[i] == key) return i
	else return -1
	========================================================================
    
public class test4순차검색_정렬된경우 {
	public static void main(String[] args) {
		int[] A= {2,4,7,9,11,19,23};
		
	}
	
	public static int sequentialSearch(int[] A, int key) {
		int n=A.length;
		
		int i=0;
		while (A[i]<key) {
			i++;
			
		}
		//while문을 빠져나오면
		//A[i]>=key(키를 찾았거나 못 찾았다면 정렬된 경우라서 더 이상 볼 필요 없는 경우)
		
		if (A[i]==key) return i; 
		else return -1;	
		
		
	}
}

이진 검색

자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

// 찾았으면 true, 못찾았으면 false를 반환한다.

binarySearch(A, key)
	A ← 주어진 배열
	n ← 주어진 배열의 크기
	key ← 찾고자 하는 값
	
	start ← 0
	end ← n - 1
	
	while(start <= end) {
		middle ← (start + end) / 2
		
		//종료:A[middle]==key 값을 찾은 경우 / start>end 
		//반복:start<end / start==end
		
		if(A[middle] == key) return true;
		else if(A[middle] > key) end = middle - 1;
		else start = middle + 1;
	}
	return false;
    ===================================================================
    package test04;

public class test3이진검색 {
	public static void main(String[] args) {
		int[] A= {2,4,7,9,11,19,23};
	}
	
	public static boolean binarySearch(int[] A, int key) {
		int n=A.length;
		
		//가장 처음에는 전체 구간을 대상으로 시작
		int start=0;
		int end=n-1;
		
		while (start<=end) {
			//일단 가운데가 우리가 찾는 값이라고 가정
			int middle=(start+end)/2;
			
			if (A[middle]==key) return true;//운좋게 가운데 값이 중간 값이었다면
			else if(A[middle]>key)end=middle-1;
			else start=middle+1;//찾는 값이 오른쪽에 있다면
				
			}
		//while문을 빠져나오면 start>end
		return false;
	}
}