[ 자료구조 ] 선택 정렬 이진 검색 배열

[자료구조] 선택 정렬 이진 검색 배열

 

알고리즘은 어떤 일을 하는 절차를 말한다. 컴퓨터. 분야의 문제 중에서 가장 방법이 많고 많이 쓰이는 알고리즘이 정렬(Sorting)이다. 정렬은 흩어져있는 데이터를 키 값(주민등록번호, 학번 등)을 이용하여 순서대로 열거하는 알고리즘이다. 선택 정렬은. 선택 정렬은 n개의 데이터를 놓고 가장 작은 수를 골라 정렬될 장소에 이동한다.

 

<선택정렬 1 주의할 점>

-배열을 함수로 넘길 때는 포인터를 사용해 배열의 이름만 넘겨서 사용한다.

-값을 하나씩 비교한다.

 

<선택정렬 2 주의할 점>

- temp 매개변수를 사용해 값을 하나씩 교환한다.

- 이중 for 문의 두번째 루프에서 값이 11 차이 나도록 설정한다.

이유 : 마지막 번째의 경우를 고려하기 전에 이미 오름차순 정렬이 되어있기 때문이다.

 

 

컴퓨터 분야의 문제 중에서 가장 방법이 많고 많이 쓰이는 알고리즘은 검색(Searching)이다. 검색(Search) : 데이터(정렬이 안된 데이터, 정렬이 된 데이터)에서 키 값이 해당되는 n개의 데이터를 검색한다. 가장 간단한 검색 알고리즘은 선형 검색(Sequential Search) 알고리즘이다. n알고리즘이다. n개의 데이터를 놓고 한 개씩 검색하는 방법이다. 데이터가 정렬이 된 상태에서는 이진 검색(Binary Search) 방법이 더 효율적이다. 이진 검색은 전체 데이터의 중간에 있는 데이터를 비교하면서 찾는 데이터가 앞/뒤 중 어디 있는지 알 수 있다. 이진 검색은 데이터를 n번 검색할 때마다(1/2)^n씩 데이터양이 줄어든다. 따라서 점점 범위를 좁혀나간다.

 

 

 

728x90

 

 

<주의할 점>

 

-left > right이면 범위를 벗어나기 때문에 -1의 값을 반환한다.

-return -1;은 통상적으로 반환 값이 없다는 것을 의미한다. 즉, 배열에 찾고자 하는 값이 없다는 것을 의미한다.

-(left/right)/2 평균값을 낼때 소수점 아래 값은 생략한다.

-선형검색보다 이진 검색이 더 효율적이다.

-인덱스 값을 반복적으로 변화시키면서 알고리즘을 작성해보자.

 

 

리스트는 일상 생활에서 가장 많이 쓰이는 자료 형태이다. 배열은 컴퓨터 언어헤서 리스트를 저장하는 데이터 타입이다. 리스트와 배열은 같은 개념이지만 다른 차원의 용어이다. 순서를 유지하는 배열에서 데이터의 삽입과 삭제가 일어난다. 배열에 새로운 값을 삽입하면 나머지 값들을 한 칸씩 이동시킨다. 배열에 값을 삭제하면 나머지 값을 한 칸씩 이동시킨다.