소스코드가 궁금하신 분들은 아래 링크를 참고해주세요! cafe.naver.com/geekbleofficial/16910 --- 시간복잡도란? 간단히 예를 들어 설명하면 n개의 블록이 있을 때 이것을 정렬하는 데 필요한 시간의 관계를 함수로 표현한 것입니다. 주로 O(n), O(n^2), O(nlogn)과 같이 표현을 하며 빅-오 표기법이라고 합니다. 위에 표기한 함수를 해석하면 O(n)은 n개의 블록을 넣었을 때 n만큼의 시간이 걸린다 O(n^2)은 n개의 블록을 넣었을 때 n^2의 시간이 걸린다 정도로 해석할 수 있습니다. 그렇다면 O(n)은 O(n^2)보다 왜 더 빠른 것일까요? 빅-오 표기법의 시간복잡도는 보통 아래와 같이 비교됩니다. O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn) > O(1)의 순서이며 만약 이해가 가지 않으시다면 n에 10을 넣어서 계산한 값을 비교하면 위와 같은 순서가 되는 것을 알 수 있습니다 . (10^2 > 10 ) 즉, O(2^n)으로 갈수록 시간복잡도는 크다는 뜻이며 O(1)은 반대로 시간복잡도가 가장 적으며 그것은 곧 빠르다는 의미입니다. 그러므로 다시 영상으로 돌아가 이번에 정렬 알고리즘을 살펴보면 선택, 삽입, 버블 정렬은 O(n^2)이며 병합, 퀵 정렬은 O(nlogn)이기 때문에 시간복잡도를 보고 병합, 퀵 정렬이 더 빠르겠다는 예상을 할 수 있게 됩니다. ( O(n^2) > O(nlogn) 이기 때문에.. )
선택정렬 정렬 끝부분에 맞는걸 일일히 하나씩 골라서 정렬 삽입정렬 정보들을 정렬 사이사이에 알맞은곳에 집어넣어 정렬 버블정렬 정보들을 맞은쪽으로 조금씩 이동시키며 정렬 병합정렬 삽입정렬을 4개 나눠서 하고 그걸 합쳐서 2개로, 2개를 합쳐 하나로만들어 정렬 퀵정렬 병합정렬이랑 어찌보면 비슷한 방법으로 비슷한것끼리 계속 모아가면서 정렬
퀵정렬도 조금 설명이 애매하고 병합정렬은 아예 설명이 틀린거같은데요? 일단 병합정렬에는 삽입정렬 개념이 안들어가있습니다 만약 단순히 삽입정렬을 작은 묶음으로 나눠서 하는 방법이었다면 시간복잡도가 똑같이 O(n^2)이어야 맞는데 병합정렬은 시간복잡도가 O(nlogn)입니다 엄연히 다르죠. 그리고 그 묶음이 4개일 이유도 없습니다. 원래 병합정렬 시작에는 묶음이 자료의 개수만큼 존재합니다. 퀵정렬은 비슷한 것끼리 모아가면서 한다고 할 수도 있겠지만 정확히는 기준점이 되는 데이터를 하나 골라둔 뒤에 그 기준점보다 작은 데이터와 큰 데이터 두 묶음으로 나눕니다. 그리고 이렇게 만들어진 두 묶음에서 각각 다시 똑같은 일을 반복하게되면 마지막에는 결국 데이터가 정렬이 되는 원리입니다
버블정렬 1번째 자료를 2번째 자료랑 비교하고, 2번째 자료랑 3번째 자료를 비교하고, 3번째 자료를 4번째 자료랑 비교하고... 이걸 다 정렬될 때까지 합니다. 퀵정렬 기준이 되는 자료를 하나 잡습니다. 그걸 기준으로 작은 자료는 왼쪽, 큰 자료는 오른쪽으로 정렬시킵니다. 그럼 2등분이 되겠죠. 2등분 된 왼쪽에서 또 기준이 되는 자료를 잡습니다. 그걸 기준으로 작은 건 왼쪽, 큰 건 오른쪽으로 정렬. 그럼 또 2등분이 되겠죠. 이런 작업을 계속 하는 방식입니다.
민바크님 영상 잘 보고있습니다. 흥미로운 영상들 많이 만들어주셔서 감사합니다 =] 제 진로가 게임프로그래머여서 민바크님께 한가지 여쭤보고싶은게 있습니다. 현재 저는 고2 진학중이고 방과후 활동에서 C언어를 배우고 있는데 진로를 위해 C언어 학습을 그만두고 바로 유니티부터 배우는게 더 나을까요?
소스코드가 궁금하신 분들은 아래 링크를 참고해주세요!
cafe.naver.com/geekbleofficial/16910
---
시간복잡도란?
간단히 예를 들어 설명하면 n개의 블록이 있을 때 이것을 정렬하는 데 필요한 시간의 관계를
함수로 표현한 것입니다.
주로 O(n), O(n^2), O(nlogn)과 같이 표현을 하며 빅-오 표기법이라고 합니다.
위에 표기한 함수를 해석하면
O(n)은 n개의 블록을 넣었을 때 n만큼의 시간이 걸린다
O(n^2)은 n개의 블록을 넣었을 때 n^2의 시간이 걸린다
정도로 해석할 수 있습니다.
그렇다면 O(n)은 O(n^2)보다 왜 더 빠른 것일까요?
빅-오 표기법의 시간복잡도는 보통 아래와 같이 비교됩니다.
O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn) > O(1)의 순서이며
만약 이해가 가지 않으시다면 n에 10을 넣어서
계산한 값을 비교하면 위와 같은 순서가 되는 것을 알 수 있습니다
.
(10^2 > 10 )
즉, O(2^n)으로 갈수록 시간복잡도는 크다는 뜻이며
O(1)은 반대로 시간복잡도가 가장 적으며 그것은 곧 빠르다는 의미입니다.
그러므로 다시 영상으로 돌아가 이번에 정렬 알고리즘을 살펴보면
선택, 삽입, 버블 정렬은 O(n^2)이며
병합, 퀵 정렬은 O(nlogn)이기 때문에 시간복잡도를 보고
병합, 퀵 정렬이 더 빠르겠다는 예상을 할 수 있게 됩니다.
( O(n^2) > O(nlogn) 이기 때문에.. )
어우야
나 자세히 보기 괜히 누른거 같애...
중간에 'O(n)과 O(n^2)은 왜 더 빠른 것일까요?'는 말이 좀 이상한 거 같은데요?
워메
10은 같은게 있는듯 하여..
100을 대입하면
암산해서 틀렸을 수도 있습니다.
2^n=2^100=겁나 큼 아무튼 큼
n^2=100^2=10000
nlogn=100x2=200
n=100
logn=2
1
(2^n)>(n^2)>(nlogn)>n>logn>1
(혹시 몰라 말하는 거지만 ^는 제곱을 말합니다.)
잘은 모르지만 수능 국어 비문학 기술 지문에 딱이군요!!
시간복잡도 개념, 선택정렬 과 다른 정렬 비교대조, 문제점과 해결방법 정반합...ㅋㅋㅋㅋ
수능 비문학에 왜 이런 지문을 내는거여...
틀린것을 고르시오 내기 딱좋자너
@@minbgames 저는 비문학으로 인터넷뱅킹의 원리ㅇ 대해 나왔는데요 뭘
암호 문자의 원리가 그렇기 심오한지 처음앎
물리 중간쯤에 나오는 상대성이론같은 뭐시기도 그냥 나와버리는데 안나올거란 보장은 없긴 하죠 ㅋㅋㅋㅋㅋㅋㅋㅋ
정렬알고리즘... 알고리즘을 배울때 가장 처음 재우는 알고리즘이죠ㅎㅎ
@@dokdokddok ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
@@dokdokddok 역시 잡내가 나면 알고리즘을 제대로 배울 수가 없죠..
그래서 알고리즘 수업 들으면 졸렸던거구나
김재우씨 나와주세요.
와 감사합니다.
이렇게보니깐 이해하기 쉽네요 학교때 배울때 뭐라는지 이해안갔는데 이거보니깐 이해하기 쉽워지긴하네요
삽입정렬은 내폰의 비밀번호를 까먹었을때 하나하나대입하는것과같군
약4일 정도걸려서 풀었다
원리도 설명해 주면 더 좋았을 텐데
인정.
퀵정렬특 : 분할정복! 분할정복! 분할정복! 분할정복! 분할정복! 분할정복! 분할정복! 분할정복! 분할정복! 분할정복!
솔직히 c++ 쓰는 분들은 퀵정렬이고 뭐고 그냥 std sort 쓰죠 :yum:
5번은 이해할 시간은 있냐
으악 정렬이라닛 ㅋㅋㅋㅋ 학교 댕길때 빡시게 했던 기억이 ㅋㅋ
역시 게임제작은.. 알고리즘과 수학.. 사실은 근데 유니티가 다 해주죠ㅋㅋ
ㅋㅋㅋㅋ 이번 작업복 영상애서 얼굴 너무 잘봤습니다 ㅋㅋㅋㅋㅋㅋ
@@불꽃놀이-d7e 공교육으로 그렇게 배우는 코딩은 말이 코딩이지 별 의미 없다고 보시면 됩니다..
혹시 기수정렬 알고리즘을 LuaU로 어떻게 짜는지 아시나요?
병합정렬은 데이터를 어디에서 어디까지 지정하고 병합해서 그 속에서 오름차순으로 정렬하고 나머지도 똑같이 하고 정렬된 그룹을 다시 정렬하는걸로 보였음
그그 전혀 다른 예시 같지만
카드 두 그룹으로 나누고
츄롸라라라ㅏㄱ 하면서 섞는 그그
그거랑 느낌 비슷할거같애
@@Wolf_call 리플 셔플이요
그니까 컴퓨터가 알고리즘을 사용해서 5=7 을 만드는 영상이군요
1:23 점점 빨라지는거 킬포
학교발표자료에 사용해도 되나요?
딴건 눈으로 봐도 어떤식으로 정리하는 지 대충 감이 오는데, 버블정렬은 잘 모루겠숴...
그냥 뒷쪽부터 정렬하는거아님?.?
시간복잡도는 최악조건과 최고조건에따라 달라질수있습니다.
단적인예로 최고조건에서 버블정렬은
시간복잡도가 가장 우수합니다!
맞아여 조건에 따라 데이터량에 따라 유리한 소팅방법이 다르죠 ㅎㅎ
거희 정렬된 상태에선 삽입이 제일 우수하지 않나?
@@네활어회트월킹을할줄 나도 그런줄알았는뎅
최고조건을 따지는건 그다지 무의미하지 않을까요?
틀렸어요 버블정렬은 배열이 이미 정렬되어 있는 상태라도 무의미한 순환을 계속합니다. 최선의 경우도 복잡도는 n^2이에요. 최고조건에서는 삽입정렬이 제일 우수합니다
와우 퀵정렬이 괜히 퀵이 아니구나 ㄷㄷ
사실 quick sort는 최악의 경우 n^2의 시행횟수를 가지게 되죠 즉, O(n^2)입니다
ㄹㅇㅋㅋ
삽입과 선택은 속도가 비슷하겠네요. 처음에 빠르냐 나중에 빠르냐의 차이인듯
퀵 정렬: 기준점을 잡은 뒤 파티션 알고리즘으로 기준점을 올바른 위치로 이동.
그 후 나뉘는 두 부분을 가자고 다시 반복
가장 빠르면서도 효율적인 스탈린 정렬을 소개하지 않다니 너무하군요
데이터 소실이 정렬입니까...
해외에서 저런거 모아놓은 영상 계속 유튭 추천영상에 떠서 뭔지 궁금했는데 이제 이해하고 갑니다!!
아 이거 유투브에서 잊을만하면 추천영상으로 뜨던 그거네
각 정렬마다 어떤 방식으로 하는지 설명해주시면 좋겠네요
스탈린 정렬은 O(n)
뒤에 작은게 있다? 없애버리면 됩니다
아래에서 위로 스캔은 불가능한건가요??
그러면 높이를 인식하니까 한번스캔하면 다 될거같은데
이번학기에 배웠던 알고리즘...이걸 먼저 봤더라면 성적 뒤에 +붙어서 a+이 될수있었을까...
그러면 a였다는 거네요.
...높은데?
어지간한 상황에서는 (피봇을 잘 고르도록 만든) 퀵정렬이 같은 O(n log n)중에서도 빠르죠
정보처리기사에서 이론을 글자로만 봤는데.... 이런거 넘모 좋네요 ㅎㅎ
와 이거 대학교에서 데이터구조론에서 배운건데 여기서 보니까 너무 반갑네요 ㅋㅋㅋ
선택 삽입 버블 정렬의 알고리즘은 이해되는데 남은 2개는 이해가 안되네요
전공자는 아니지만 재밌네요
재귀의 개념이 들어가서 그럴거에요
정렬중에 가장 빠른 정렬은 "좌우로 정렬" 입니다
c#은 몰라도 삽입 정렬이 맘에 드네여♥
크흠...
ㅗㅜㅑ
안 섞으면 되지 꼭 뭘 섞어난 그래서 퀵 담에 병합이 좋은거 같네요
Bogo Sort 였나 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 랜덤으로 정렬해서 맞을때까지 정렬하는거 ㅋㅋㅋㅋㅋ
멍청이 정렬 (stupid sort) 라고도 하죠
시간복잡도 무한대 ㅋㅋ
보고보고 정렬도 있어요ㅋㅋㅋ
보고정렬이 길면 장보고정렬ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
음~~~ 3번부터 어떻게 하는건지 모르겠다~~
집청소하는것도 퀵정렬로 빠르게 정리되었으면 좋겠는데
ㅇㅈ
그 다음 청소기행
유튭에 삐오오 소리내는 영상이 이런거구나
시뮬레이터 아떤거 사용하세요?
O(n)의 기수정렬도 있었다면 좋았을것 같네요
이런 프로그램은 대체 뭘쓰시는건가요?? 혼자 가지고 놀아보고싳은데..
선택정렬
정렬 끝부분에 맞는걸 일일히 하나씩 골라서 정렬
삽입정렬
정보들을 정렬 사이사이에 알맞은곳에 집어넣어 정렬
버블정렬
정보들을 맞은쪽으로 조금씩 이동시키며 정렬
병합정렬
삽입정렬을 4개 나눠서 하고 그걸 합쳐서 2개로, 2개를 합쳐 하나로만들어 정렬
퀵정렬
병합정렬이랑 어찌보면 비슷한 방법으로 비슷한것끼리 계속 모아가면서 정렬
퀵정렬도 조금 설명이 애매하고 병합정렬은 아예 설명이 틀린거같은데요?
일단 병합정렬에는 삽입정렬 개념이 안들어가있습니다 만약 단순히 삽입정렬을 작은 묶음으로 나눠서 하는 방법이었다면 시간복잡도가 똑같이 O(n^2)이어야 맞는데 병합정렬은 시간복잡도가 O(nlogn)입니다 엄연히 다르죠. 그리고 그 묶음이 4개일 이유도 없습니다. 원래 병합정렬 시작에는 묶음이 자료의 개수만큼 존재합니다. 퀵정렬은 비슷한 것끼리 모아가면서 한다고 할 수도 있겠지만 정확히는 기준점이 되는 데이터를 하나 골라둔 뒤에 그 기준점보다 작은 데이터와 큰 데이터 두 묶음으로 나눕니다. 그리고 이렇게 만들어진 두 묶음에서 각각 다시 똑같은 일을 반복하게되면 마지막에는 결국 데이터가 정렬이 되는 원리입니다
@@creep8867 전 야매라서요
버블 보고 정수학의 버블 수열이 생각나서 컴공1도 안한 야매가 씨부려보자면
_다음 개체와 비교하며 앞 개체의 변량이 크면 위치를 반전시킨다. 막히면 다시 처음부터한다_ 라고 유추 해 봤는데 맞나요?
퀵소트는 머지소트와 비슷하지 않구요. 퀵은 피봇을 기준으로 더 높은 값과 낮은 값으로 계속해서 분리하는거지 비슷한 값끼리 모으는게 아녜요
ㅗㅜㅑ 야매댓글 불탄다
선택 정렬밖에 모른다...
누가 버블부터 원리 설명좀.
행님 STL sort는 어떤 알고리즘을 쓰길래 복잡도가 nlogn보다 낮나요
거희 정렬된건 선택을 써서
정렬하는 동영상 은근 중독성 있던데
오 신기하네
유튜브가 나를 여기로 이끈것도 알고리즘이 속하지
페이지 뒤섞인 프린트 정리하는거랑 크게 다를게 없네 ㅋㅋ
보는건 버블 정령이 가장 좋다
짜는것도 간단하긴 합니다
섞는 순서를 고대로 역행만 하면 젤 빠를텐데^^; 전부 기억해뒀다가 필요한 순서만 빼내서 활용하는 기능은 언제 나올까요..?
섞는 것도 랜덤이라 젤 효율적으로 섞진 않았을테니... 완전 무관하군요. 역시 수학은 과정무시... 결과에서 항상 시작해야...
저는 버블정렬외에는 아무것도 몰랐습니다 정말 위대합니다 선생!
나 이거 유튜브 알고리즘에 걸려서 막대기 길이가 섞이고 정렬되고 색깔이 섞기고 정렬되는 영상 수없이 많이봤는ㄷ
ㄹㅇㅋㅋ
알고리즘 공부 할때 저런 영상을 봤는데 구현할줄을 꿈에도 몰랐습니다 ㅋㅋ; 정말 대단하시군요!
답답해서 2배속으로 봄
선택정렬이랑 삽입정렬,병합,퀵은 이해했는데 버블정렬은 어떤원리지...
버블정렬은 7 1 8 9 5 이렇게있으면
앞에서부터 2개씩 비교해 나가는거에요~
(7 1)8 9 5
1 (7 8) 9 5
1 7 (8 9) 5
1 7 8 ( 5 9)
한바퀴돌았으면 또 계속해서 반복 해나아가는거에요~
정렬이고 뭐고 일단 편----안
0:43한국인이 쓰러지는속도
3:25한국인이 극혐하는속도
3:40한국인이 환장하는속도
배속을 하시면 기분이 좋아집니다
근데 섞을때 이상한 효과음 나는거는 만국 공통이에요??
컴퓨터가 삽입을 잘하군
중간에 보다가 포기했어요
알고리즘이 날 이 알고리즘 영상으로 이끌었다...
내일모레 기사를 봐서 그런가 알고리즘이 여기로 이끄네
우와...어떻게 영상이 10초만에 이해지 못할 수가 있지.. ..
선택 정렬 알고리즘..
앞에까진 이해했는데... 병합정렬, 퀵 정렬은 이해가 안됨....ㅜㅜ 병합은 3개로 나눠서 정렬한 다음 마지막으로 최종 정렬하는건가..? 근데 퀵정렬은 찐으로 모르겠다...
적절한 원소 하나를 기준(피벗, pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은 것, 큰 것으로 나눈뒤 나누어진 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬하는거에요
초등학생때 c++할때 기억나네요
기억난김에 코드업 하면서 놀아야게따
아주 하나 하나 비교해서 하는거구만!!
마지막 퀵정렬은 너무빨라서 무슨매커니즘인지 잘 모르겟네...
기준이 되는 피봇값(보통 중간에 있는 값을 씀)으로 더 큰 값과 더 작은 값으로 숫자들을 나눕니다. 그러면 피봇 기준으로 양 옆에 2개의 숫자 배열이 생기는데 이때 2개 숫자 배열을 각각 정렬하면 결과적으로 정렬이 끝나겠죠. 이걸 계속 반복하는 정렬입니다.
6 3 7 5 1 2 9 (정렬 대상)
[3 1 2] 5 [6 7 9] (5를 기준으로 나눔)
[1 [3 2]] 5 [[6] 7 [9]] (각각 1과 7을 기준으로 나눔)
[1 [2 3]] 5 [[6] 7 [9]] (정렬 대상이 2개면 단순히 정렬, 하나라면 정렬 끝)
@@woolyung 오 이해가 잘되는 설명 감사합니다.
민바크님 건강하게 지내세요~~
감사합니다!!
그래서 왜 저렇게 정리하는지 원리 깊게 알려주세요!
물리엔진군 한국 버전
3:46 브금 뭐에요?
최적화의 중요성 이려나
일본에도 이런비슷한 과학 물리유튜버있던데 재밌덩데
만바크님도 재밌게만드시네요 그리고 ㅋㅋ한국어만드셔서 더 좋군요
비슷하게 탐색 알고리즘도 가능하신가요?
이 외에도 정렬 알고리즘은 여러가지가 있습니다.
ruclips.net/video/vmT3XUBoxiQ/видео.html
(해당 링크 영상의 마지막에 있는 LSD 정렬을 한 번 보세요 소리가 아름답습니다)
썸네일 비트코인 차트인줄알았네
버블정렬이랑 퀵정렬이 잘 이해가 안가요 ㅠㅜ
버블정렬
1번째 자료를 2번째 자료랑 비교하고, 2번째 자료랑 3번째 자료를 비교하고, 3번째 자료를 4번째 자료랑 비교하고... 이걸 다 정렬될 때까지 합니다.
퀵정렬
기준이 되는 자료를 하나 잡습니다. 그걸 기준으로 작은 자료는 왼쪽, 큰 자료는 오른쪽으로 정렬시킵니다. 그럼 2등분이 되겠죠.
2등분 된 왼쪽에서 또 기준이 되는 자료를 잡습니다. 그걸 기준으로 작은 건 왼쪽, 큰 건 오른쪽으로 정렬. 그럼 또 2등분이 되겠죠.
이런 작업을 계속 하는 방식입니다.
민바크님 영상 잘 보고있습니다. 흥미로운 영상들 많이 만들어주셔서 감사합니다 =]
제 진로가 게임프로그래머여서 민바크님께 한가지 여쭤보고싶은게 있습니다.
현재 저는 고2 진학중이고 방과후 활동에서 C언어를 배우고 있는데 진로를 위해 C언어 학습을 그만두고 바로 유니티부터 배우는게 더 나을까요?
군대가서 하는 좌우로 정렬! 이 제일 빠름
시각적으로 보니 신기하네여
삽입정렬 게임깔때 진행속도같당
크 컴공도 아닌데 교양때 저거 한다고 애먹었었는데ㅋㅋ
보고정렬해주세요
오오.. 유튜브 알고리즘에 대한 영상이군요!!
아닌데여
눈으로 보니 정말 잼있네요
역시 퀵... 마지막에 병렬 영상으로 4~8분할 해서 비교해 주셔도 좋을거 같습니다.
카운팅빠다죠
추억이 새록새록
이걸 알고리즘으로 들어왔다
앍...선택정렬.... 너무 느렭...
내가 문서 순서대로 정리 할 때 수작업으로 한 알고리즘이 삽입정렬이었굼
자료구조 내용이네...
이론상 한방에 가능한 보고 정렬!
저거 알고리즘에 떠서 본건데 이런 내용 이였구ㄴ
정렬이라길래 순간 흠칫해버렸다..
정렬은 bogo...
퀵 원리가 뭐누
빅오 개념을 여기서... ㅋㅋㅋㅋㅋㅋ