Skip to main content

Sorting Methods

Image
Sorting which is one of topic in data sructure is an important thing in real life for facilitate the data management. Data sorting can be implemented by ascending order or descending order. There are some methods for data sorting such as:
  • Insertion Sort
  • Selection Sort
  • Bubble Sort
  • Quick Sort
1. Insertion Sort
Straight insertion is a sorting method which takes a parenthesis data on ordered data and shoves data which is bigger than parenthesis data so parenthesis data can be placed on right place. For example, there is an array that contains these number :
3 12 2 4 13 5
If the data above is sorted in ascending by straight insertion, the result is:
Parenthesis Data Sorting Result
12
3 12 2 4 13 5
In 1st loop, 2nd data of array becomes parenthesis data, then being compared with all previous data (3). If there is no data which is bigger than parenthesis data, there is no data that will be shove backward.
2
3 12 2 4 13 5
In 2nd loop, 3rd data of array becomes parenthesis data, then being compared with all previous data (3, 12). There are two data which are bigger than parenthesis data so those data will be shoved one step backward and put parenthesis data at 1st place.
4
2 3 12 4 13 5
In 3rd loop, 4th data of array becomes parenthesis data, then being compared with all previous data (2, 3, 12). This data will be placed at 3rd place.
13
2 3 4 12 13 5
In 4th loop, 5th data of array becomes parenthesis data, then being compared with all previus data (2, 3, 4, 12). Because there is no data that bigger than the parenthesis data so the parenthesis data still be in the 5th place.
5
2 3 4 12 13 5
In 5th loop, 6th data of array becomes parenthesis data, then being compared with all previous data (2, 3, 4, 12, 13). This data will be placed at 4th place.
Result
2 3 4 5 12 13

2. Selection Sort
This method is a sorting method that will look for smallest or biggest value depend on ascending or descending order then being placed at the forefront place. After that, it will look for the next smallest or biggest value along all elements of array reduced by 1, and so on. For example, there is an array that contains these number :
3 12 2 4 13 5
If the data above is sorted in ascending by selection method, the result is:
Minimum Value Sorting Result
2
3 12 2 4 13 5
In 1st loop, it will look for smallest value between 1st and 6th element of array. 2 is the smallest value so its place will be switch with 1st element.
3
2 12 3 4 13 5
In 2st loop, it will look for smallest value between 2nd and 6th element of array. 3 is the smallest value so its place will be switch with 2nd element.
4
2 3 12 4 13 5
In 3rd loop, it will look for smallest value between 3rd and 6th element of array. 4 is the smallest value so its place will be switch with 3rd element.
5
2 3 4 12 13 5
In 4th loop, it will look for smallest value between 4th and 6th element of array. 5 is the smallest value so its place will be switch with 4th element.
12
2 3 4 5 13 12
In 5th loop, it will look for smallest value between 5th and 6th element of array. 12 is the smallest value so its place will be switch with 5th element.
Result
2 3 4 5 12 13

3. Bubble Sort
This method will switch two element continously until sorting has been finished. This method is not efficient but easy to be realized.
3 12 2 4 13
If the data above is sorted in ascending by bubble sort method, the result is:
Note Sorting Result
1st loop, compare 1st and 2nd element. Because 1st is smallest than 2nd so there is no exchange
2 12 3 4 13
2nd loop, compare 2nd and 3rd element. Because 3rd is smallest than 2nd so there is exchange between 2nd and 3rd
2 12 3 4 13
3rd loop, compare 3rd and 4th element. Because 4th is smallest than 3rd so there is exchange between 3rd and 4th
2 3 12 4 13
4th loop, compare 1st and 2nd element. Because 1st is smallest than 2nd so there is no exchange
2 3 4 12 13
And so on until 16th loop. Why it is until 16th loop. It has been sorted at 4th loop. Because there are 5 element so there must be 4 exchange process for each term and also must be done 4 times to ensure that all elements has been sorted.
Result
2 3 4 12 13

4. QuickSort
This method will make a data table that will be sorted into two parts which are traced from left and from right. For example, there is an array that contains these number :
3 12 2 4 13 5
If the data above is sorted in ascending by selection method, the result is:

Step Notes
1
  • Array will be traced from left and from right.
  • Array[1] is the first element from the left, then it will trace from the right to the left to find smaller value than Array[1].
  • Array[3] which is smaller than Array[1] will be switched.
  • Array[2] is next element from the left. Array[6] which is smaller will be switched.
2
  • We have sub-array. There is no switching because Array[1] is smaller than Array[2].
  • Array[3] is first element from the left of new array, then it will trace from the right. There is no smaller value than Array[3] so there is no switching.
3
  • When we move Array[3] to left sub-array, we know that there is no smaller value than it at right sub-array.
  • At left sub-array, Array[1] as the first element will be compared with another element from the right to the left. But, we don't get any value, so Array[1] must be the smallest value.
  • Array[2] and Array[3] are switched.
  • First element of right sub-array is Array[4]. After tracing from right to left, there is no smaller value than Array[4], so it will be move to left sub-array then.
  • Second element of right sub-array is Array[5]. It will be compared with last element from the right. Because it is bigger, Array[5] is switched by Array[6] 
4
  • We have gotten Array[1] and Array[2] sorted.
  • Array[3] and Array[4] will be switched after being traced.
  • Next, there is no smaller value than Array[5] at right sub-array so there is no switching.
5
  • From the third step, we know that there is no smaller value than Array[4] in right sub-array, so after it is switched with Array[3] at fourth step, it must be sorted.
  • Array[6] is smallest value and there is no smaller value, so it also must be sorted.


Referensi : Belajar Pemrograman dengan Bahasa C++ dan Java - Shalahuddin dan Rosa
Labels:

Comments

Post a Comment

Popular posts from this blog

Rangkaian Sensor Infrared dengan Photo Dioda

Keunggulan photodioda dibandingkan LDR adalah photodioda lebih tidak rentan terhadap noise karena hanya menerima sinar infrared, sedangkan LDR menerima seluruh cahaya yang ada termasuk infrared. Rangkaian yang akan kita gunakan adalah seperti gambar di bawah ini. Pada saat intensitas Infrared yang diterima Photodiode besar maka tahanan Photodiode menjadi kecil, sedangkan jika intensitas Infrared yang diterima Photodiode kecil maka tahanan yang dimiliki photodiode besar. Jika  tahanan photodiode kecil  maka tegangan  V- akan kecil . Misal tahanan photodiode mengecil menjadi 10kOhm. Maka dengan teorema pembagi tegangan: V- = Rrx/(Rrx + R2) x Vcc V- = 10 / (10+10) x Vcc V- = (1/2) x 5 Volt V- = 2.5 Volt Sedangkan jika  tahanan photodiode besar  maka tegangan  V- akan besar  (mendekati nilai Vcc). Misal tahanan photodiode menjadi 150kOhm. Maka dengan teorema pembagi tegangan: V- = Rrx/(Rrx + R2) x Vcc V- = 150 / (1...
7 comments
Read more

Configuring Swap Memory on Ubuntu Using Ansible

If we maintain a Linux machine with a low memory capacity while we are required to run an application with high memory consumption, enabling swap memory is an option. Ansible can be utilized as a helper tool to automate the creation of swap memory. A swap file can be allocated in the available storage of the machine. The swap file then can be assigned as a swap memory. Firstly, we should prepare the inventory file. The following snippet is an example, you must provide your own configuration. [server] 192.168.1.2 [server:vars] ansible_user=root ansible_ssh_private_key_file=~/.ssh/id_rsa Secondly, we need to prepare the task file that contains not only the tasks but also some variables and connection information. For instance, we set /swapfile  as the name of our swap file. We also set the swap memory size to 2GB and the swappiness level to 60. - hosts: server become: true vars: swap_vars: size: 2G swappiness: 60 For simplicity, we only check the...
3 comments
Read more

API Gateway Using KrakenD

The increasing demands of users for high-quality web services create the need to integrate various technologies into our application. This will cause the code base to grow larger, making maintenance more difficult over time. A microservices approach offers a solution, where the application is built by combining multiple smaller services, each with a distinct function. For example, one service handles authentication, another manages business functions, another maintains file uploads, and so on. These services communicate and integrate through a common channel. On the client side, users don't need to understand how the application is built or how it functions internally. They simply send a request to a single endpoint, and processes like authentication, caching, or database querying happen seamlessly. This is where an API gateway is effective. It handles user requests and directs them to the appropriate handler. There are several tools available for building an API gateway, su...
Post a Comment
Read more

Deploying a Web Server on UpCloud using Terraform Modules

In my earlier post , I shared an example of deploying UpCloud infrastructure using Terraform from scratch. In this post, I want to share how to deploy the infrastructure using available Terraform modules to speed up the set-up process, especially for common use cases like preparing a web server. For instance, our need is to deploy a website with some conditions as follows. The website can be accessed through HTTPS. If the request is HTTP, it will be redirected to HTTPS. There are 2 domains, web1.yourdomain.com and web2.yourdomain.com . But, users should be redirected to "web2" if they are visiting "web1". There are 4 main modules that we need to set up the environment. Private network. It allows the load balancer to connect with the server and pass the traffic. Server. It is used to host the website. Load balancer. It includes backend and frontend configuration. Dynamic certificate. It is requ...
Post a Comment
Read more

Installing VSCode Server Manually on Ubuntu

I've ever gotten stuck on updating the VSCode server on my remote server because of an unstable connection between my remote server and visualstudio.com that host the updated server source codes. The download and update process failed over and over so I couldn't remotely access my remote files through VSCode. The solution is by downloading the server source codes through a host with a stable connection which in my case I downloaded from a cloud VPS server. Then I transfer the downloaded source codes as a compressed file to my remote server through SCP. Once the file had been on my remote sever, I extracted them and align the configuration. The more detailed steps are as follows. First, we should get the commit ID of our current VSCode application by clicking on the About option on the Help menu. The commit ID is a hexadecimal number like  92da9481c0904c6adfe372c12da3b7748d74bdcb . Then we can download the compressed server source codes as a single file from the host. ...
Post a Comment
Read more

Deliver SaaS According Twelve-Factor App

If you haven't heard of  the twelve-factor app , it gives us a recommendation or a methodology for developing SaaS or web apps structured into twelve items. The recommendation has some connections with microservice architecture and cloud-native environments which become more popular today. We can learn the details on its website . In this post, we will do a quick review of the twelve points. One Codebase Multiple Deployment We should maintain only one codebase for our application even though the application may be deployed into multiple environments like development, staging, and production. Having multiple codebases will lead to any kinds of complicated issues. Explicitly State Dependencies All the dependencies for running our application should be stated in the project itself. Many programming languages have a kind of file that maintains a list of the dependencies like package.json in Node.js. We should also be aware of the dependencies related to the pla...
Post a Comment
Read more