이제 BootCamp 를 다녀온지 한달이 지나갔다. 참 시간이라는게 빠르면 빠르고 붙잡고 싶어도 붙잡아지지 않는다. 군대에 나오고 나서, 되게 사람들의 말을 끊어버리는 이상한 습관이 하나 생긴것같다. 가끔씩은 나의 그런 모습이 참 보기 싫어졌다는 생각이든다. 왜 그럴까? 내가 군대 가기전에 그렇게 여유로운 삶을 누렸는데, 왜 이제는 다를까? 라는 생각도 많이 들게 된다. 뭔가 포옹력이 사라진것 같기도 하고, 내가 지금 아직도 한국 적응중인가도 많이 생각 하게 된다. 최근 들어서 그 트라우마라고 생각하는 4월과 5월이 생각난다. 하지만 그랬던 시절도 이제는 그립기 시작했다.
내 친구와 함께 토요일에 밥을 먹었다. 원래는 술도 한잔 하려고 했었는데, 점심으로 약속이 잡히자, 그럴 생각도 금쪽같이 사라졌다. 사실 이 친구와 알기 시작한건 2016년 부터 시작해서, 우리 둘이 인생극장 을 찍을정도로 같이 붙어있었고 너무 잘맞는 친구였다. 그 친구와 친해지기까지는 생각보다 오래걸렸었고, 술을 마시고 나서 “우리 힘내보자! 할수 있잖아!”라는 말을 외치면서 미국 집앞에서 소리 친적이 있다. 그때는 되게 민폐라고 생각했지만, 우리 서로 사정이 있었고 힘들었던 시기에 만난거라 그 무엇보다도 큰 힘이 되었었다. 하지만, 이렇게 당당했던 친구와 나의 모습은 없었고, 둘다 미국이 그립다는 이야기만 엄청했었다. 그 친구와 나의 인생의 절반은 다른 대륙에서 살아갔었고, 한국에 들어오고 싶지 않았던 우리는 우리가 내렸던 결론에 끝을 잘 맺치지 못했던것 같다. 물론 과거는 과거였고, 추억은 추억으로 남겨져간다. 하지만 그 과거에 지금의 우리를 만들었던 좋은 추억들은 쉽사리 사라져가진 않는다는건 분명하다. 늘 우리는 서로의 생일을 챙겨주고, 맛있는 밥도 같이해서 유학생 다웠던 삶을 살아갔었다. 항상 웃어서 행복했고, 나의 아파트 발코니에서 나무와 고속도로를 넘어서 담배피면서, 맥주 한캔 했던 그런 여유로움을 나름 즐겼다. 하지만, 미국의 삶도 호락호락 하진 않았다. 나 나름 영어를 잘한다고 생각하지만, 막상 발표나 친구들과 이야기할때는 흐름이 비슷하고, 백인들과 흑인들 사이에서 콕 파묻힌 느낌도 들때도 많았지만, 그렇게 다양한 인종들끼리 친구가 됬었고, 차별을 당한적은 있지만, 그때는 그런가보다 하면서 넘겨갔던게 많았고, 풀리지 않은 문제들은 정말 혼자서 끊임 없이 붙잡으려고 포기 하지 않았다. 그랬던 삶들은 점차 점차 사라져가며, 이제는 밖에 나가면, 음식집 앞에서 사람들의 소리들이 들린다.
물론 한국의 삶은 다른 형들과 사람들의 말로는, 바쁘게 살아가고, 포기하며 살아가고, 여유롭게 살아가지 못하고 있는것 같다. 되게 호락호락 하지 않는 반면에 나는 최대한 이 미국에서 받아온 여유로움이 아직은 남아있는것 같다. 나와 친구가 했던 말이 생각난다. “우리의 몸은 한국에 있는데, 정신은 미국에서 살고 있다고.” 이 말이 정말 정확하게 맞다. 나는 이제 한국 산지 반년이 지나간다. 처음에는 적응하느라, 일하느라, 전화만 했었던 가족들이 진짜로 나의 인생에 들어오고, 많이 힘들었던건 사실이다. 그리고 책상에는 아직도 “좋은 개발자나 연구자가 되려면, 모든 순간에 열심히, 끊임없이 살아가야된다” 써놓은 포스트잇이 아직 붙여있다. 마음 한편으로는 내가 지금 살만하니까 이런 저런 잡생각들이 많아진건가? 라는 생각이든다. 사실 제일 힘든 사람은, 이런 글을 쓸수도 없을것이다. 아마 피곤해서 그냥 누워버리겠지 라는 생각이 들겠지. 하지만, 이런 잡생각도 쓰는게 나의 Life Log 아닌가? 라는 생각에 글을 쓰면서 뭔가 마음으로 안정이된다.
사실은 요즘 이런 생각이든다. 더 좋은 사람이 되어야지 라는 생각. 구체적이진 않다. 하지만, 이 좋은 사람이 된다는건 약간 이런 방향인것 같다. 사람의 말에 귀기울여 줄수 있고, 나의 고민거리를 먼저 다가서는게 아니라, 다른 사람 고민거리를 먼저 들어주고, 내 이야기를 잘 물들일수 있는 사람, 계속 몸에 여유로움이 남아 있는 사람 그리고 기다려줄수 있는 사람. 나의 과거의 모습에 이런 글을 본다고 한다면, 참 너 뭐하냐? 이런 생각이 들기도 하지만, 이제는 나이가 들어간다. 그리고 나이가 들면 들수록, 점점더 wise 한 사람이 되려면, 이런 저런것을 많이 해봐야된다고 생각한다. 그래서 지금 하고 싶은 것들이 많이 생각나다. 이거는 이번년의 나의 목표이자 하고 싶은것이다. 2022 년 12 월 31 이 되면 꼭 내 스스로에게 확인을 해보고 싶은 사항이다.
뭔가 4번은 뭔가 불문명 하지만, 꼭 부딫쳐 봐야한다. 그리고 나에게 하고 싶은 말이 있다. 너는 지금까지 잘해왔고, 분명 좋은 사람으로 거듭나기 위한 지금의 과정을 지나치고 있는거야. 책도 많이 읽어서 사람에게 너의 감정을 쉽게 들키지 말고, 슬픈것과 화나는것의 차이를 분명히 알아야될거고, 좀더 진정성있고 여유로운 사람이 될수있기를 바래. 과거는 과거일뿐이고 현재를 열심히 살아가렴. 너가 분명 이런저런 Transition 을 겪고 있는건 알지만, 이것도 하나의 step 이야, 너를 더 사랑해줄수 있는 그런 기회이며, 남들을 더 사랑을 나눠줄수있고, 귀를 열수 있는 그런 사람이 되길 바래.
아직 나는 20 대 이고, sometimes you gotta say fuck to the world. It’s fine to be that way, just kin on your instinct okay?! Also, just forgot to mention I love you Nick! Keep working hard alright!
나는 3/17 - 4/7 일까지 논산훈려소로 3주 하는 훈련소를 갔다왔다. 사실 3.10 일 쯤 이미 마음의 준비는 끝났었지만, 가기전에 코로나가 걸려서 3.17 으로 미뤄졌다 전문연구요원으로 훈련소 가는 준비는 여기를 참고하면서 준비물을 준비했지만. 마음도 마음인지라 시계도 챙겨가지 않았다. 불침번이라걸 내가 할까? 라는 생각에… (속히 말해 뺑뺑히 돌릴것같았는데 아니였다. 그래서 결국 분대원들의 시계를 빌려서 불침번을 섰지만) 결론적으로 말하자면 되게 불편한것도 많았지만, 나름 뜻깊은 경험이며 좋은 인연을 만났다고 생각한다. 글을 쓰면서 생각이 잘 정리는 안되지만, 최대한 느낌을 글에 잘녹여들이고 싶다.
엄마와 같이 11 시쯤 출발했을거다. 엄마는 늘 걱정하지만, 티를 안내는 성격이라 말하면서 느꼈다. 그래도, 걱정을 덜어드리려구 “엄마, 이건 거의 그냥 캠프 갔다오는거니까, 걱정하지마” 라는 말을 하고 연무대 근처에서 제대로 인사 못하고, 엄마와 안녕을 했다. 코로나 기확진자여서 따로 나뉘어서 그룹이 정해졌었다. 그렇게 기다리는 중에, 주변에 있는 사람들은 많은 긴장을 한듯해보였다. 한 2-3 시간 지나고 나서야 연대를 나누기 시작했고, 그렇게 기다리다가 캐리어를 끌고 30 연대로 향하게 되었다. 내가 갔던곳은 30 연대 12 중대 2 소대 1 분대 였으며, 번호는 1 번이다. 그렇게 1번이라는 번호는 어렸을때 부터 제일 싫어 하는 번호 였으며, 부담스러운 번호였지만 어떻게든 되겠지 하며, 분대 안에 들어갔다.
사실 우리 분대원의 나이는 조사할때 부터 알고 있어서 나보다 위 93 두명 제외하고 다 어렸다는 생각을 계속하고 있었다. 물론 나이를 생각하는게 지금 생각해보면 조금 꼰대 같았지만, 뭔가 내공있는 모습을 보여주고 싶어서 바로 나는 분대원들이랑 인사와 자기소개를 먼저 해서, 점차 점차 친해졌었다. 처음에 분대안에서 보급품을 나눠주는데, 모포 와 베게를 주는데.. 와 역시 군대구나 어떻게 잘까? 라는 생각이 들었고, 관물대 안에는 헬멧, 물통, 등 이있었다. 그때서야 나는 군대에 들어왔구나라는 생각이 들었다.
코로나 기확진자여서, 10일 정도 격리를 하며, 밥은 식판에 식비늘을 끼어서 밥을 먹었었다. 참고로 군대밥은 나쁘지 않았다(밥을 너무 많이 줘서 문제였지만). 또 뭔가 습관처럼 국에다가 밥을 말아먹는 습관이 생기더라, 참 이상하게 국물이 없으면, 아침에 6시반에 밥이 넘어가지 않았었다. 불침번은 총 14명이 돌아가면서 홀수 번호로 돌아갔었다. 그 말은 즉슨 첫날에 내가 불침번을 섰었다는거다… 완전 1시간 반동안 계속 서있는건 WOW..
격리중에 여러가지 책을 받았었는데, 하나는 학습장이였고, 다른 하나는 잘 기억은 안나지만 그것은 약간 현역들에게 주어지는 날짜 카운트식으로 일기를 쓰도록 하는 책이였다. 사실 그 책은 두껍기도 하고 별로 쓰고싶지 않았다. 그래서 나는 학습장에 매일 매일 일기를 쓰기 시작하며, 편지도 쓰기 시작했다. 조금 아쉽고, 조금 서운하기도 한건 가족들이나 친구들에게 인편을 받지 못했다는 점인데, 사실 보니까 내가 연대나 중대를 말하지도 않아서 못보냈다고 한다. 또 지금 생각해보면, 딱히 서운할게 없는게 매일 10 분 정도 휴대폰을 받았다는거 였다. 마지막주에는 주지도 않았지만, 그 끝나기전 3일에 주긴 했지만.
막상 PCR 2차 검사를 한 이후에, 격리가 풀려서 모든게 자유로울것 같았지만 분대장(조교)들이 절반 가까이 코로나에 걸렸다고 한다. 와 그때는 정말 안심과 아쉬움이 있었다. 일단 조금 두려웠던 각개는 하기 싫었지만, 체력 시험? 에 팔굽혀 펴기 1 급과 윗몸일으키기 는 1급을 받고 싶어서 매일 분대원과 돌아가면서 40 개 해서 하루에 200 개 정도 했었고, 또 나의 29의 목표에 맞게 뭔가 이루고 싶었는데 이런 부분에서는 되게 아위웠다. 분대장들이 코로나에 걸리니, 밖같에는 여러 책들이 있었다. 이미 가지고 온 2 책은 다읽었었고, 다른 책을 찾아보다가, 소설을 보게되었는데, 그 소설의 이름은 “불편한 편의점”. 내가 사실 소설을 별로 유용하지도 않고, 뭐 정보같은것도 안주기때문에 좋아하진 않았는데, 그 책은 내가 읽기에 너무 편안한 느낌도 있었고, 흠 거의 평점을 5 점만점에 5 점을 주고 싶었다. 그리고 다른 한 책은 Metaverse 라는 책이였는데, 이 책도 되게 괜찮았다. 딱 잘 주제 별로 잘 나눠졌었고, 나름 코로나가 한창인 이 시대에 되게 걸맞는 정보를 담고 있던 책이였다. 이상하게 군대에서 할게 없어서, 계속 책보는게 웬지 모르게 나의 과거를 돌아보게되고, 생각이 깊어지기도 하면서, 감정적으로 여러생각을 하게 되서, 내가 가지고 있던 편입견들이 점점 없어지고 좀 더 부드러워지는 느낌이였다.
잠은 항상 12 시에서 1 시에 자서, 10시에 자는게 되게 힘들었었다. 아무생각 안하고 코를 고는 분대원들이 조금 부럽기도 했지만, 나는 항상 일기를 썼었다. 생각을 매일 정리한다는 느낌이, 생각많은 나에게 짐을 덜어주었었다. 그리고 매일 같이 기도 했다. 특정한 사람들을 위해서, 보살펴주고 계속 지켜봐달라고, 힘들때 나의 넘쳐나는 에너지를 전해달라고, 이 3주 훈련 잘 보낼수 있게 도와달라며, 기도를 했었다. 사실 조금 기독교와 먼 삶을 살아오긴 했지만, 그래도 기도하는건 나의 걱정들을 조금씩 덜어주긴했다.
조금 현타왔던건 PX 를 가는데, 벛꽃이 정말 많이 폈었다. 계속 분대내에서 있다보니 현타가 씨게 왔지만 그 나름대로 걷는게 즐거웠다. PX 는 총 두번을 갔는데, 왜 그때는 R.O.K.A 티가 너무 이뻐보이더라… 그래서 4벌이나 사버렸다.. 그리고 부모님과 친구들 선물로 화장품에 관련된거 샀었다… 총 금액은 한 15 만원 정도 샀는데, 진짜 지금 오면 좋은 추억이 될것 같다.
사실 이 글을 쓰다보니까, 여런 저런 추억들이 있는데, 너무 많기도 하고, 여런저런 면에서 귀찮기도 하다. 하지만, 이 추억들은 되게 소중히 간직될것같다. 고생도 안했고, 거의 격리만 한것같은데도 불구하고, 이런저런 면에서 분대원 동생들에게 배우고, 내가 이때까지 생각했던것들이 어느정도 정리된 느낌도 있었으며, 몸도 한츰 건강해진것 같아서 정말 좋은 경험이였다.
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
If we sort this, the duplicates must be adjacent each other. The built-in function for sort() in c++ is based on Quick Sort() the average time complexity is n*log(n). The worst case for quick sort can be n^2 which is the brute force way.
Can we make it better ? We can use HashSet because to insert, and look up takes O(1). The process are following: we push the data to the set. if we have seen the data for incoming element, return true, otherwise keep inserting. Time Complexity in this case would be O(N), space would be O(N) as well, but worst case would be all unique elements
Reviewing what I studied, how this work will be explained as well.
Separate Chaining: A Collision Resolution Technique in Hashing
Separate chaining is indeed one of the most common collision resolution techniques used in hash tables. As a technical engineer who has implemented this in several projects, I can confirm it’s both elegant and efficient when properly configured. This algorithm can be seen as an extension of bucket sort.
Let’s break down how it works: Hash Function: We use a hash function to determine which slot a key should go into. For example, if we have a value 0.84, we might use a floor operation as our hash function, resulting in slot 8. Collision Handling: However, hashing can lead to collisions. For instance, values like 0.32, 0.39, and 0.31 would all hash to slot 3 using our floor operation. This is where collision resolution comes in.
Separate Chaining vs Open Addressing:
In Open Addressing, when a collision occurs, we would need to find open spots for each value, often by probing linearly through the table. Separate Chaining takes a different approach. Instead of linear probing, it allows multiple keys to be stored in the same slot using a linked list. This is why it’s called “separate chaining” - each slot in the hash table can chain together multiple values in a separate linked list. This approach efficiently handles collisions by allowing multiple elements to exist at the same index of the hash table. There are also different chaining technique like cuckoo hashing (which results O(1) if implemented properly)
The key advantage of separate chaining is that it degrades gracefully under a high load factor and doesn’t require the frequent resizing that open addressing might. However, it does require additional memory for the linked list pointers.
How Separate Chaining Works
In separate chaining, each slot of the hash table points to a linked list that stores all elements hashing to the same location. When a collision occurs (multiple keys map to the same index), we simply add the new element to the linked list at that particular index
Implementation
#include<iostream>
#include<iomanip>
#include<string>usingnamespacestd;structNode{stringkey;intval;Node*next;};classHashTable{public:HashTable(int_size):size(_size){hash_table=newNode*[size];for(inti=0;i<size;i++){hash_table[i]=nullptr;}}~HashTable(){for(inti=0;i<size;i++){Node*p=hash_table[i];if(p!=nullptr){Node*chain=p->next;while(chain!=nullptr){Node*target=chain;chain=chain->next;deletetarget;}deletep;hash_table[i]=nullptr;}}}Node*insert(stringkey,intval){Node*new_node=newNode();new_node->key=key;new_node->val=val;intidx=hash(key,size);new_node->next=hash_table[idx];hash_table[idx]=new_node;returnnew_node;}boolremove(stringkey){intidx=hash(key,size);if(hash_table[idx]->key.compare(key)==0){Node*target=hash_table[idx];hash_table[idx]=hash_table[idx]->next;deletetarget;returntrue;}for(Node*p=hash_table[idx];p->next!=nullptr;p=p->next){if(p->next->key.compare(key)==0){Node*target=p->next;p->next=p->next->next;deletetarget;returntrue;}}returnfalse;}Node*get(stringkey){intidx=hash(key,size);for(Node*p=hash_table[idx];p!=nullptr;p=p->next){if(p->key.compare(key)==0)returnp;}returnnullptr;}voiddisplay(std::stringmsg){cout<<msg<<endl;// Traverse the entire hash tablefor(inti=0;i<size;++i){cout<<" +--------+--------+"<<endl;cout<<i<<" |";Node*p=hash_table[i];if(p==NULL){// NULL record, print emptycout<<" "<<setw(6)<<""<<" | "<<setw(6)<<""<<" |";}else{// Print the record from the tablecout<<" "<<setw(6)<<left<<p->key<<" | "<<setw(6)<<right<<p->val<<" |";// Traverse and print the chainfor(p=p->next;p!=NULL;p=p->next){cout<<" --> "<<"[ "<<p->key<<" | "<<p->val<<" ]";}}cout<<endl;}cout<<" +--------+--------+"<<endl<<endl;}private:inthash(stringkey,intsize){inthash=0;for(inti=0;i<key.size();i++){hash+=key[i];}returnhash%size;}Node**hash_table;intsize;};intmain(){HashTablecustomers(8);// Insert key-value pairscustomers.insert("Alice",101);customers.insert("Bell",102);customers.insert("Max",103);customers.insert("Evin",104);customers.insert("Ana",105);customers.insert("Dave",106);customers.insert("Leo",107);customers.display("HASH TABLE after insertion of customers 'Alice', 'Bell', 'Max', 'Evin', 'Ana', 'Dave', and 'Leo'.");// Delete key-value pairscustomers.remove("Dave");customers.remove("Ana");customers.remove("Max");customers.display("HASH TABLE after deletion of customers 'Dave', 'Ana', and 'Max'.");}
Time Complexity
Average Case
Search: O(1 + α) where α is the load factor (number of elements divided by table size)
Insertion: O(1 + α)
Deletion: O(1 + α)
For a successful search, approximately 1 + (α/2) links need to be traversed on average.
Worst Case
Search: O(n) when all keys hash to the same bucket
Insertion: O(n) in the pathological case where all elements end up in one chain
Deletion: O(n) since deletion requires searching first
I called this as range is because we find the first occurence(location within the range) from left to right, and second occurence from right to left, then we return the total count from that range.
intCount(constvector<int>&vec,intx){constintn=vec.size();inti=BinarySearch(vec,0,n-1,x);if(i==-1)return;// we find the first oneintcount=1;intleft=i-1;while(left>=0&&arr[left]==x){count++;left--;}intright=i+1;while(right<n;&&arr[right]==x){count++;right++;}returncount;}
Reviewing what I studied, how this work will be explained as well.
Radix Sort is similar to Counting Sort, but it handles different types of inputs. Consider the array vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };. If we were to sort this array using comparison-based sorts like Merge Sort or Quick Sort, we would achieve a time complexity of O(N log N). However, as we know from Counting Sort, we can achieve a linear time complexity of O(N) under certain conditions.
How it works
Radix Sort leverages a similar approach to achieve efficient sorting. The key idea is to sort numbers digit by digit, starting from the least significant digit (ones place) to the most significant digit. To do this, we need a placeholder for each digit (0 through 9). We iterate through each digit position (ones, tens, hundreds, etc.) and sort the numbers based on that digit.
Let’s implement Radix Sort similarly to Counting Sort. The crucial part is indexing each digit. The expression count[a / exp % 10] returns the index for each digit. We then increment this count. After counting, we accumulate these counts to determine the positions where each number should be placed, just like in Counting Sort.
Finally, we iterate through the array from right to left (last index to first). For each number, count[temp[i] / exp % 10] - 1 gives us the index where the number should be assigned in the sorted array. We subtract 1 because array indices start at 0.assigned.
voidCountingSort(vector<int>&arr,intk,intexp){vector<int>temp=arr;// copyvector<int>count(k+1,0);for(autoa:arr)count[a/exp%10]+=1;for(inti=1;i<count.size();i++)count[i]+=count[i-1];Print(count);for(inti=arr.size()-1;i>=0;i--){arr[count[temp[i]/exp%10]-1]=temp[i];count[temp[i]/exp%10]--;}}voidRadixSort(vector<int>&arr){intk=9;// from 0 to 9intm=*max_element(arr.begin(),arr.end());for(intexp=1;m/exp>0;exp*=10){CountingSort(arr,k,exp);Print(arr);}}vector<int>arr={170,45,75,90,802,24,2,66};RadixSort(arr);
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Now what we want is basically convert Romans to Integer. How can we solve it. If we have all those unique values stored in some dictionary, then we can check whether we could use those integer and sum it up. The special case would be two letter associated for example IV which is 4. (V - I). With this logic, we can solve it by two approaches.
If we have all those unique values stored in dictionary, then we need to handle the single one, then the two letter one. The time complexity would be the string size (N).
classSolution{public:intromanToInt(strings){std::map<string,int>roman={{"I",1},{"V",5},{"X",10},{"L",50},{"C",100},{"D",500},{"M",1000},{"IV",4},{"IX",9},{"XL",40},{"XC",90},{"CD",400},{"CM",900}};if(s.length()<=0&&s.length()>16)return0;inti=0;intsum=0;while(i<s.length()){// Two String Handleif(i<s.length()-1){stringdoubleStr=s.substr(i,2);if(roman.count(doubleStr)){sum+=roman[doubleStr];i+=2;continue;}}// OneStringstringsingleStr=s.substr(i,1);sum+=roman[singleStr];i+=1;}returnsum;}};
Okay, let’s think further more. For example, if we have DXCI, then we can calculate D + (C - X) + I or CMXCIV = (M - c) + (c - x) + (v - i), which is very useful in the logic. Also, let’s not use all those special cases which are the two letters combination.
If we have MCMXCIV, when we think about this problem, we can see that M + (M - C) + (C - X) + (V - I). This case, the constraint is if [i+1] > [i], then we subtract [i], else we add. Then, we can simply get the code above.
Reviewing what I studied, how this work will be explained as well.
Bucket Sort is a sorting algorithm that is similar in concept to Radix Sort and Counting Sort, but it is designed to handle floating-point numbers. Like these other algorithms, Bucket Sort uses placeholders to sort elements efficiently. However, unlike Radix Sort, which sorts integers digit by digit, Bucket Sort distributes floating-point numbers into buckets and then sorts each bucket individually.
Time Complexity
The time complexity of Bucket Sort can vary depending on the distribution of the input data. In the best case, where the numbers are uniformly distributed, the time complexity can be O(N + K), where N is the number of elements and K is the number of buckets. However, if the numbers are not well-distributed and most elements end up in a single bucket, the time complexity can degrade to O(N^2) due to the sorting algorithm used within each bucket.
Steps to Implement Bucket Sort
Divide Data into Buckets: If there are N data points, divide them into K buckets. Ideally, K should be close to N for optimal performance.
Distribute Elements into Buckets: Place each element into its corresponding bucket based on its value.
Sort Each Bucket: Use a sorting algorithm like Insertion Sort to sort the elements within each bucket.
Merge Sorted Buckets: Combine the sorted elements from all buckets to produce the final sorted array.
Implementation
Here’s an example implementation of Bucket Sort for floating-point numbers. We’ll consider a simple case with 10 buckets and the input array { 0.78f, 0.17f, 0.39f, 0.26f, 0.72f, 0.94f, 0.21f, 0.12f, 0.23f, 0.67f }.
// Insertion SortvoidInsertionSort(vector<float>&bucket){for(inti=1;i<bucket.size();++i){floatkey=bucket[i];intj=i-1;while(j>=0&&bucket[j]>key){bucket[j+1]=bucket[j];j--;}bucket[j+1]=key;}}voidBucketSort(vector<float>&arr,intnum_buckets){vector<vector<float>>buckets(num_buckets);// Put Bucketfor(auto&a:arr){intindex=int(a*num_buckets);buckets[index].push_back(a);}for(inti=0;i<buckets.size();i++){InsertionSort(buckets[i]);}// update arr from sorted bucketintindex=0;for(inti=0;i<buckets.size();i++){for(intj=0;j<buckets[i].size();j++){arr[index++]=buckets[i][j];}}}
The time complexity for this case is O(N^2), the space complexity is O(1) is because we’re traversing vector twice with the size of N. The vector itself doesn’t take any space, so its O(1). Normally, in this case. We can make it by O(n) for time complexity and space complexity is O(n) by using hash map.
classSolution{public:vector<int>twoSum(vector<int>&nums,inttarget){unordered_map<int,int>hash;intn=nums.size();for(inti=0;i<n;i++){intx=target-nums[i];if(hash.find(x)!=hash.end()){return{hash[x],i};// order doesn't matter}hash[nums[i]]=i;}return{};}};
if we switch some logic, which is int x = target - nums[i]; to int x = nums[i] - target;, then we can get the index of the two numbers that add up to the target. By using the dictionary, we can get the index of the two numbers that add up to the target. If we find the number, we can return the index of the two numbers. If we don’t find the number, we can add the number to the dictionary.
Reviewing what I studied, how this work will be explained as well.
Counting Sort is a sorting algorithm that works by counting the number of objects that have each distinct key value, and using arithmetic to determine the positions of each key value in the output sequence. It’s like creating a histogram of the data by counting the number of occurences of each key value.
How it works
Create a count array to store the count of each unique number (the size would be the highest integer + 1)
Count the occurences of each element in the input array and store it in the count array.
Add the previous count to the current count to get the position of the element in the output array.
Create the ouptut array to store the sorted elements.
In Reverse order of output array, place the input array’s element in the output[count[input[i]] - 1] index, and update the count of the element in the count array. (which is subtracting 1 from the count)
