선택정렬,삽입정렬,이진탐색

선택정렬이란

배열의 첫번째 값부터 마지막 값까지 하나씩 선택하고 선택한 값 또는 이미 정렬된 부분을 제외한 나머지 부분들 중 최소값 또는 최대값을 찾아서 위치를 교환하는 알고리즘

특징

시간복잡도 : 데이터의 크기가 커질수록 성능이 급격히 저하된다.

공간복잡도 : 배열 내에서 값의 위치를 변경하기 때문에 추가적인 메모리를 차지하지 않는다.

안정성 : 배열 안에 같은 값이 있는 경우 정렬 후 위치가 유지되지 않는다 EX) 배열 값 {7,5,2,5} -> 정렬 후 {2,5,5,7}

장/단점

구현이 간단하고, 값의 이동 횟수가 적어 메모리 최적화가 필요할 때 유리함 / 효율성이 낮아 큰 배열에는 적합하지 않습니다.

동작과정

1. 배열의 첫 번째 값부터 나머지 값 중 가장 작은 값을 찾아 첫 번째 값과 교환합니다.
2. 두 번째 값부터는 이미 정렬된 첫 번째 값을 제외하고, 남은 부분에서 가장 작은 값을 찾아 두 번째 위치에 배치합니다.
3. 이 과정을 배열의 마지막 값까지 반복합니다.

삽입정렬이란

배열의 모든 요소를 앞에서부터 차례대로 정렬된 배열과 비교하여 자신의 위치를 찾아
삽입함으로써 정렬을 완성하는 알고리즘이다.

장점
코드가 어렵지 않고 단순하며 이해하기 쉽다.
크지 않은 소규모 배열의 데이터를 임시로 정렬할 때 가장 적합하다.
동일한 값의 항목 순서가 유지되어 데이터가 섞여도 원래 위치를 보장한다.
이미 정렬된 데이터에서 효율적이며 메모리 부담이 적다.
배열이 일부 정렬된 상태로 시작하면 가장 빠르게 정렬된다.

단점
배열의 데이터 수가 많고 크기가 크면 사용하기 어렵다.
역순 배열(정렬되지 않은 데이터가 많은 경우)일수록 최악의 시간 복잡도를 보인다.
시간 복잡도:
최고의 경우(베스트 조건): 세 가지 정렬 방식 중 가장 빠르다.
최악의 경우: 정렬되지 않은 상태에서는 많이 느리다.
평균적으로는 세 가지 정렬 방식 중 그나마 빠른 편에 속한다.

이진탐색이란

정렬된 리스트에서 특정 값의 위치를 찾아내는 알고리즘이다.

시간 복잡도: 로그 N (log N)이다.
로그 N은 1부터 N의 N제곱까지의 시간 복잡도 중 굉장히 빠른 알고리즘에 해당한다.
리스트가 길어질수록 걸리는 시간이 비례하여 줄어드는 특징을 가진다.

탐색 방식 예시 (목표값 13): 9칸짜리 정렬된 배열에서 목표값 13을 찾는 과정이다.
중간값 설정: 배열 길이 9를 2로 나누어 4.5에서 나머지를 제외한 4가 중간 인덱스가 된다.
중간값과 목표값 비교: 중간값 7과 목표값 13을 비교한다.

범위 축소: 목표값 13이 중간값 7보다 크므로, 중간값 7을 포함하여 그보다 작은 값들은 후보에서
탈락시킨다.
인덱스 재설정: 일반적으로 재귀 함수를 사용하지만, 학습 한계로 인해 변수를 따로 만들어 인덱스를
5, 6, 7, 8로 재지정한다. 반복 탐색: 축소된 배열에서 다시 중간값을 찾아 목표값과 비교한다.

탐색 종료: 중간값이 목표값과 같아지면, 플래그 값(flag)이 true가 되면서 탐색이 종료된다.
탐색 실패 예시 (목표값 18): 배열 안에 목표값이 없는 경우를 설명한다.
목표값 18이 배열의 어떤 중간값과 비교해도 찾을 수 없으며, 계속해서 범위를 축소한다.
최종적으로 남은 인덱스 8에서, 시작 인덱스와 끝 인덱스의 차이가 0보다 작아지면 (예: -1), 배열
탐색이 종료된다.
탐색이 종료되었음에도 목표값을 찾지 못하면 플래그 값(flag)이 false로 바뀌고, 사용자에게 "값이
배열에 없습니다"라고 알려준다.