[수업기록] 알고리즘 : list(검색, 선택 정렬)

240801 파이썬반

 

1. 검색

1) 개념 : 저장되어있는 자료 중에서 원하는 항목을 찾는 작업

 

2) 종류 :

- 순차 검색

: 일렬로 되어있는 자료를 순서대로 검색하는 방법 -> list 배열 검색, 단 검색 대상 수가 많으면 수행시간 비효율

: 2가지 경우가 있음(정렬되어 있는 경우, 정렬x)

 

: 정렬되어 있지 않는 경우 ->

: 처음부터 끝까지 해당 원소 찾아보고 인덱스 반환, 찾지 못하면 검색 실패(통상 -1 반환)

: 평균 시간복잡도 O(n)  : (1/n) * (1+2+3+..+n) = (n+1)/2

 

: 정렬되어 있는 경우 (오름차순, 내림차순) -> 

: 하나씩 순회하면서, 해당 순회 값이 찾고자 하는 값보다 크면, 찾는 원소가 없는 것으로 판단하고 검색 종료

: 평균 시간복잡도 O(n)

def sequentialSearch(a,n,key): #n : arr 길이
	i  = 0
    while i<n and a[i]<key: 
    	i += 1
    if i<n and a[i] == key: #위 while문에서 a[i]< key가 false일때 실행 🤔🤔
    	return i
    else:
    	return -1

 

 

- 이진 검색

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

: 조건 -> 이진 검색을 위해선 자료가 정렬된 상태여야 함! 

: 시간복잡도 : logN

ex. 이진 검색으로 7을 찾는 경우

arr = [2,4,7,9,11,19,23]

# 1. 가운데 숫자를 찾는다 
# 2. 가운데 숫자(찾고자 하는 값보다 큰 숫자면)를 기준으로 더 작은 쪽을 검색범위로 두고 찾는다
# 3. 찾았을 때 없으면, 검색 범위에서 새로 가운데 숫자를 찾고, 
# 4. 새로 찾은 가운데 숫자가 찾고자 하는 값보다 크면 오른쪽 검색을 한다
# 5. 만일 오른쪽 검색시 배열의 끝이면, 검색 실패!(찾고자하는 값이 없는 걸로)

# 배열 길이 가운데 찾는 법 (start + end) // 2

# 이진검색 TIP : 시작점과 끝 점을 파악해라

# 코드로 구현 🤔

def binarySearch(a,N,key):
	start = 0 #주어진 구간의 시작 인덱스
        end = N-1 # 마지막 요소의 인덱스
    
    while start <= end: #남은 구간이 있다면 !!!!
    	middle = (start + end) // 2 #가운데 숫자의 인덱스 찾기
        if a[middle] == key: #검색 성공
        	return true
            
        elif a[middle] > key: #찾고자 하는 key값보다 크다면
        	end = middle - 1 
        else:
        	start = middle + 1 
    return False # 검색실패

# 재귀함수 이용하여 구현
# 재귀 : 같은 작업을 반복 -> 속도가 더 빠름

def binarySearch2(arr, low, high, key):
	if low > high : # 검색실패
    	return False
    else:
    	middle = (1ow + high) // 2 #중간숫자 인덱스
        if key == arr[middle] # 검색성공
        	return 	True
        elif key < arr[middle]:
        return binarySearch2(a, low, middle-1, key) 🤔
        
        elif arr[middle] < key:
        return binarySearch2(a,middle+1, high, key) 🤔

 

 

- 인덱스

: 원본 베이터에 배열 인덱스 추가한 경우 -> 원본 데이터에 데이터가 삽입될 경우, 상대적으로 크기가 작은 인덱스 배열을 정렬하기 때문에 속도가 빠름(대용량 데이터 매번 정렬X)

 

: 인덱스란 용어는 database에서 유래했고, 테이블에 대한 동작 속도를 높여주는 자료 구조를 말함

: db 인덱스는 이진 탐색 트리 구조로 되어있음

---

2. 선택 정렬 : '계속 최솟값을 찾고, 왼쪽으로 배치시켜라'

1) 장점 : 코드가 단순(버블정렬도 마찬가지) -> 교환 횟수가 버블, 삽입 정렬보다 작다

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

3) 과정 : 주어진 리스트 중 최소값 찾고 -> 그 값을 리스트 맨 앞에 위치한 값과 교환 -> 맨 처음 위치를 제외한 나머지 리스트를 대상으로 반복

4) 단점 : 시간복잡도가 높은 편(O(n2))

arr[0] = min_idx #arr 맨 앞 애를 제일 작은 애로 치고 시작

[i+1:] #맨 앞자리 제외한 미정렬 원소들 순회 코드

def selection_sort(arr, N) : # arr 정렬대상 # N 크기
	# 주어진 구간에 대해 기준 위치 i를 정하고 
    for i in range(N-1):     # 왜 N-1 까지? 🤔 -> 인덱스 n-2 까지 순회 -!!
    min_idx  = i #최소값 위치를 기준인자로 가정 
        for j in range(i+1, N): #남은 원소에 대해 실제 최소값 위치 검색 #i 다음값부터 인덱스 끝까지
        	if arr[min_idx] > arr[j] :
            	min_idx = j #인덱스 업데이트
        arr[i], arr[min_idx] = arr[min_idx], arr[i] #자리 바꾸기


a = [2,7,5,3,4]
b = [4,3,2,1]
seleciton_sort(a,len(a))
seleciton_sort(b,len(b))
print(a)
print(b)

#예제. n번째로 작은 원소 찾는 방법(큰 원소 찾기도 가능)

#1번부터 k번째까지 작은 원소들을 찾아 배열 앞쪽으로 이동, 배열 k번째 반환

def SelectionSort(a,k):
	for i n range(0,k ):# 🤔 k개씩 고려
    		min_idx = i #기준위치를 최소값 위치로 가정
        	for j in range(i+1, len(a)): # 🤔인덱스 끝까지
    			if a[min_idx] > a[j]:
        			min_idx = j
                a[i], a[min_idx] = a[min_idx], a[i] #가장 최소값 찾아서 가장 왼쪽으로 정렬
	return arr[k-1] # 🤔 배열(인덱스) 때문에 -1