(이코테 2021 강의 몰아보기) 4. 정렬 알고리즘

[@박형민-f7t]

추석 연휴동안 몰아서 잘 보고있습니다! 좋은 강의 감사합니다:)

[@everythingship9949]

영상 감사히 잘 봤습니다. 대기업 코딩테스트를 준비하는데 있어서 정렬 알고리즘은 강의에 나온 4가지만 알고 있어도 충분한가요 ? 정처기에서 나오는 버블 정렬 등은 필요하지 않는지 궁금합니다 !

[@양민혁-m1i]

파이썬의 경우 sort 내장 라이브러리가 있는데 혹시 이러한 정렬 알고리즘이 활용될 때 sort를 사용하지 말라는 그런 문제에 대비를 하는 건가요??

[@hosid40]

영상 감사드립니다! 덕분에 다시 재밌게 공부하고 있습니다. 궁금한 게 있어서 실례를 무릅쓰고 댓글 남깁니다. 퀵 정렬에서 내부 loop 가 while(right > start and array[right] >= array[pivot]): 을 사용 하셨는데, while(right > start and array[right] > array[pivot]): 으로 안 하신 이유가 있을까요?( 오른쪽 비교 연산자를 >= 로 쓰게 되면, pivot 값들이 여러 개라면, left partition과 right partition 에 모두 있게 될 거 같아 보여서요. 최종 결과값은 문제가 없을 거 같긴 한데, 다른 이유가 있나 궁금해서 질문 드립니다. :)

[@띠용-l3j3r]

이미 1년이 지났지만.. 그냥 댓글 달아보면 실수인 것 같습니다 pivot 기준으로 양쪽다 >= = 하고 하나는 < 하거나 가 맞을 것 같네요

[@jongphago]

등호가 없으면 left와 right가 엇갈리지 않아 무한루프에 빠집니다. 첫번째 루프의 종료조건은 left와 right가 엇갈릴때 입니다. 두번째 세번째 루프에서 left와 right를 옆으로 미뤄줘야 하는데, pivot과 right 배열 값이 같을때 등호가 없게되면 두번째 세번째 루프에 진입을 못하여 else 문만 반복하여 실행하게 됩니다. [1, 1]배열로 테스트 해보시면 문제가 되는 사례를 찾으실수 있습니다.

[@taeyann6153]

@@jongphago 한참 고민하다가 여기서 해결하고 갑니다. 감사드립니다!

[@jo8020173]

11:47 삽입정렬에서 else break 꼭 필요한가요..?

[@coldwisdom]

좋은 강의 감사합니다. 열심히 볼께요. (1회 완강)

[@user-fc5ow6lq3m]

선택 on2 가장작은거찾아서 앞으로, 삽입 2번째부터시작,왼쪽으로 이동스왑 on2, 이미정렬되잇으면on, 퀵 onlogn 일반적 피봇첫번째로 한후 왼쪽오른쪽 체인지, 교차시 작은거랑피봇바꾼후 분할., 최악은on2>정렬되잇을때, 편향된분할일어날수잇음, 표준라이브러리에 퀵정렬은 최소nlogn 보장,(피봇값다른거설정한듯?) , 계수정렬 인덱스에 개수카운트입력(양수형데이터? 제한된조건에선 퀵보다빠름 on+k)-동일한데이터 여러개등장할떄유리,0 999 2개등장할때는 불리.

[@smj7173]

python 표준라이브러리 정렬은 quick sort가 아니라 merge와 insert 조합해서 만든 Tim sort로 구현되어있어서 최악일때도 O(n log n)을 보장합니다. 확실하진 않지만 제가 stackoverflow 토론에서 본 글에 따르면 quick sort에서의 pivot selection은 분명 확률적으로 최악의 케이스인 경우를 줄이지만 케이스가 작아도 결국 최악의 경우 시간복잡도는 O( n^2)입니다.

[@회계법인노예]

두배열의 원소교체 (마지막 문제) 를 만들어봤는데요.. 저는 sort를 for문으로 구현해서 했는데.. 코드좀 봐주실수있나요 정상작동합니다. N = int(input()) K = int(input()) a = list(map(int,input().split())) b = list(map(int,input().split())) for i in range(len(a)): min = i for j in range(i+1, len(a)): if a[min] > a[j]: min = j a[i], a[min] = a[min], a[i] for i in range(len(b)): min = i for j in range(i+1, len(b)): if b[min] > b[j]: min = j b[i], b[min] = b[min], b[i] for i in range(1, K+1): if b[len(a)-i] > a[-1 + i]: b[len(a)-i] , a[-1 + i] = a[-1 + i], b[len(a) -i] result = sum(a) print(result)

[@byehi981]

좋은 강의 감사합니다 5:20에서 나온 알고리즘을 실행해보니 답과 같이 나오지 않아서 # 스와프 줄 밑에 min_index = i를 추가하였습니다. 코드를 이렇게 수정해야하는게 맞는지 확인부탁드립니다.^^

[@archeage_villain]

영상 잘 보고 있습니다! 38:51 마지막 문제는 idx = 0 if A[i] = B[idx] swap(A[i], B[idx]) idx += 1 와 같이 되어야 최대값이 나오지 않을까 싶습니다!

[@minholee7084]

저도 그렇게 생각했었는데, 이미 a는 오름차순, b는 내림차순으로 정렬을 해서 반례없이 a < b가 아니라면 break를 해도 되지 않을까요? 저도 이제 막 공부중이라 틀렸다면 죄송합니다!

[@leeyoungjeon0511]

선택정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내는게 맞지 않나요?? 책에서는 N-1번으로 되어있는데 강의에는 N번으로 되어있네요 외부 루프의 경우 마지막 원소는 정렬이 되지 않기 때문에 N-1이 맞지 않나 생각합니다

[@이상헌-e1r]

파이썬으로 퀵정렬 구현한 코드에서 def quick_sort(arr): if len(arr)

[@user-fl9xt3se9o]

왼쪽은 빈 리스트가 나올뿐 따로 None으로 지정되지 않습니다.

[@spectrum8200]

for i in range(len(list)): for j in range(i+1, len(list)): if list[i] > list[j]: list[i], list[j] = list[j], list[i] 위 코드처럼 선택정렬을 min=i없이 구현하면, 어떤 문제가 생길까요? list 넣고 돌려봤는데 문제가 없어 보여서요

[@yeojhye]

계수정렬부터

[@dkapqk450]

잘보고갑니다

[@thugken]

15:30

[@mr_chu_CERT]

15:34