Today, I'll show you something about Data Structures and Algorithm
[This post is not finished yet. I'll keep you posted: I'll upload a
software that has implemented all of the alogrithm mentioned., so you
can play with it to get a better understanding of these sort algorithm.
Further conents are:
Big O notation
Stacks
Queue
Heap ]
Bubble Sort
This algorithm goes through the unsorted list from left to right and compares two neighboring elements. If the left member is bigger than the right one, then the algorithm swap their position. It will repeat this until it reaches the end. Then it wll starts from the beginning and repeats the mentioned procedure. But this time it will not go to the very end of the whole list, because the last element is already the biggest element, but the next to last one.
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
public void bubbleSort(){
for (int i= arraySize-1; i >=0; i--){
for (int j=0; j < i; j++){
if ( Integer.valueOf((String) myModel.getValueAt(j, 1)) > Integer.valueOf((String) myModel.getValueAt(j+1,1))){
swap(j,j+1);
}
}
}
}
Selection Sort
Selection sort goes through the unsorted list and selects the smallest member of the unsorted list and puts it at the end of the sorted list. After that it repeats the process: It selects the smallest member out of the unsorted list and append this member at the sorted list of the first smallest member that he found. The algorithm repeats this process until there are no members to be found in the unsorted list but all of them are in the sorted list. This algorithm is not very efficient but very easy to implement.
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
[java code that implements the sorting algorithm]
public void selectionSort(){
for (int i=0; i < arraySize; i++){
int indexOfMinValue=i;
for (int j=i; j < arraySize; j++){
if (Integer.valueOf((String) myModel.getValueAt(j, 1)) < Integer.valueOf((String) myModel.getValueAt(indexOfMinValue,1))){
indexOfMinValue=j;
}
}
if (indexOfMinValue!=i)
swap(i, indexOfMinValue);
}
}
Insertion Sort
Insertion sort takes the first member of the unsorted list and goes from behind the sorted list and puts it right after the first element that is smaller than him. Because the Insertion sort checks the first member of the unsorted list it finishes when it has reached the end of the unsorted list.
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
[java code that implements the sorting algorithm]
public void insertionSort(){
// you start with the 2nd index (i.e. index number "1")
for (int i=1; i < arraySize; i++){
//get the first one of the sorted list and compare it to the member
//at the end of the sorted list.
//int j=i;
int j=i;
String firstMemberInUnsortedList=(String) myModel.getValueAt(j, 1);
while(j>0 && Integer.valueOf((String) myModel.getValueAt(j-1, 1)) > Integer.valueOf(firstMemberInUnsortedList)){
//replace the member in j-1 with it's descendend in j
myModel.setValueAt(myModel.getValueAt(j-1, 1), j, 1);
j--;
printOutArray();
}
myModel.setValueAt(firstMemberInUnsortedList, j, 1);
}
}
Bucket Sort
The Bucket sorting algorithm is not really a sorting algorithm. Instead it's rather a prozcess to improve sorting efficiency and is Usually used in conjuction with another sorting algorithm, like insertion sort.1. In cojunction with other sorting algorithms:
The aim is to apply a sorting algorithm not to an entire list but to smaller lists. That's why in Bucket sort the elements in the big list are put into to smaller consecutive lists. E.g. if the list contains numbers that ranges from 0 to 10, then there will be several smaller lists (=buckets) let's say 3. Then the first bucket can hold numbers from 0 to 3. The second bucket from 4 to 6. And the third 7 to 10 buckets.
Now, within each of this list one of the aforementioned sorting algortihm, e.g. selction sort or insertion sort can be applied to sort the the elements within the buckets. After that all of buckets are merged into a big list again.
2. Bucket sort alone:
With Bucket sort alone you create for a large list smaller lists - exactly the same as in the example above. After that you again create smaller buckets within each buckets, until there's only one element in this bucket. These created buckets are set in order already, so when there's only one element in the bucket, you merge the buckets into a large list and get a list that is sorted.
This technique reqires recursion which in turn is costly in terms of ressources and time.
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
public void selectionSort(){
for (int i=0; i< arraySize; i++){
int indexOfMinValue=i;
for (int j=i; j < arraySize; j++){
if (Integer.valueOf((String) myModel.getValueAt(j, 1)) < Integer.valueOf((String) myModel.getValueAt(indexOfMinValue,1))){
indexOfMinValue=j;
}
}
if (indexOfMinValue!=i)
swap(i, indexOfMinValue);
}
}
Radix Sort
This sorting algorithm efficient especially for larger arrays. It's applied for non-comaritive integer sorting algortihm. There are two ways of doing it: Least Significan Digit (LSD), Most Significant Digit (MSD). This only means where to start sorting. LSD means in this context that we start with the far right digit. E.g. the far right digit of number 123 is the position where number 3 is. MSD means we start at the position where number 1 is. In the following example the focus is on LSD. We have 10 buckets. Each carries one of the values from 0 to 9. We will go through the list from left to right. Given we have 3 digit numbers, then we first look at the value of the number's first digit (since it's LSD) and put these numbers in the buckets with the same value.
E.g. The number 123 has got 3 as a first digit will be put into a bucket with the value 3. The number 456 has got 6 as a first digit and will be put into bucket 6 and so on. According to this first sort we get a new order of our list. In the next step we will look at the value of the number's second digit and put them in to the buckets with the same value.
E.g. the number 123 has got 2 as the second digt and will be put into the bucket with the value 2. The number 456 has 5 as the second digit and will be put into bucket 5 and so on. After that we get a list that again has a reordered. But we aren't done yet. In the third and last step (it's the last step because we agreed on having 3 digit numbers), we look at the 3rd digit of the numbers and will put them into the according bucket. Now after this step we get a list that is finally ordered.
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
[java code that implements the sorting algorithm]
private ArrayList< String > SortRadix(int digit, ArrayList< String> arr){
ArrayList< String> bucket_sorted = new ArrayList< String>();
if (digit==0)
return arr;
else{
ArrayList< String> bucket_0 = new ArrayList< String>();
ArrayList< String> bucket_1 = new ArrayList< String>();
ArrayList< String> bucket_2 = new ArrayList< String>();
ArrayList< String> bucket_3 = new ArrayList< String>();
ArrayList< String> bucket_4 = new ArrayList< String>();
ArrayList< String> bucket_5 = new ArrayList< String>();
ArrayList< String> bucket_6 = new ArrayList< String>();
ArrayList< String> bucket_7 = new ArrayList< String>();
ArrayList< String> bucket_8 = new ArrayList< String>();
ArrayList< String> bucket_9 = new ArrayList< String>();
// goes throught the transferred array "arr"
// and checks all of it's members
for (int i=0; i< arr.size(); i++){
//"radix" contains the digits of the current number
String[] radix=(arr.get(i).split(""));
int digi=numberOfDigit!=radix.length-1?digit-(numberOfDigit-(radix.length-1)):digit;
String nthDigit;
try{
nthDigit=radix[digi].equals("")?"0": String.valueOf(radix[digi]);
}catch(Exception ex){
nthDigit="0";
}
//check the nth Digit
switch(nthDigit){
//transfer it into the table
case "":
case "0":
bucket_0.add(arr.get(i));
break;
case "1":
bucket_1.add(arr.get(i));
break;
case "2":
bucket_2.add(arr.get(i));
break;
case "3":
bucket_3.add(arr.get(i));
break;
case "4":
bucket_4.add(arr.get(i));
break;
case "5":
bucket_5.add(arr.get(i));
break;
case "6":
bucket_6.add(arr.get(i));
break;
case "7":
bucket_7.add(arr.get(i));
break;
case "8":
bucket_8.add(arr.get(i));
break;
case "9":
bucket_9.add(arr.get(i));
break;
default:
System.out.println("case doesn't exist");
break;
}
}
//merge into one array, which is "bucket_sorted"
bucket_sorted.addAll(bucket_0);
bucket_sorted.addAll(bucket_1);
bucket_sorted.addAll(bucket_2);
bucket_sorted.addAll(bucket_3);
bucket_sorted.addAll(bucket_4);
bucket_sorted.addAll(bucket_5);
bucket_sorted.addAll(bucket_6);
bucket_sorted.addAll(bucket_7);
bucket_sorted.addAll(bucket_8);
bucket_sorted.addAll(bucket_9);
return SortRadix(digit-1, bucket_sorted);
}
}
public void radixSort(){
numberOfDigit=3;
//translate tableModel into array
String[] bucket_sorted_array=(SortRadix(numberOfDigit, tableModelIntoArrayList())).toArray(new String[myModel.getRowCount()]);
//merge array into table model
merge(bucket_sorted_array);
}
// Helper function
// transfers tableModel to array
private ArrayList< String> tableModelIntoArrayList(){
ArrayList< String> a=new ArrayList< String>();
for (int i=0; i< myModel.getRowCount(); i++){
a.add((String)myModel.getValueAt(i,1));
}
return a;
}
// transfers arrays back to tableModel
private void merge(String... args){
int m=0;
for(String arg: args){
myModel.setValueAt(arg, m, 1);
m++;
}
}
Quicksort
In Quicksort you select one element in the list and partion the list into two sets: One that only conains slements that are larger than the pivot and one that only contains elements smaller than the pivot. In order to do so, we start with a two pointers: One at the very beginning and one at the very end of the list. We move the pointer at the beginning one step up to the other end until it reaches a value that is larger than or equal the pivot. Then we move the pointer at the end one step down to the other end until it reaches a value that is smaller than or equal the pivot. When we have on the left side a value that is larger than or equal the pivot, and on the right side a value that is smaller than or equal the pivot swap the position of these elements. Then we select another element that is larger than or equal resp. smaller than and equal the pivot and swap position. This process will be repeated until both pointers will point to the same element - the pivot. At this point the pivot is in the correct position, Now, we have two sets: One that contains elements smaller than the pivot and one that contains elements that that are larger than the pivot. These two steps will be partioned like we did with the orignal list, until we get lists that are either containing zero or one element and are therefor sorted. In the last step these list, with only one (or zero) elements are rejoined into one big list containing sorted elements.
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
[java code that implements the sorting algorithm]
Merge Sort
Merge sort uses a similar concept to bucket sort. The big unsorted list is divided into list containining only one item. Then you compare the elements within these two lists and put it in another list. The element that is smaller will be put into the new list first. The larger element, will be put in second. You repeat the process for all other single element lists. Now, you don't have lists containing single elements but lists containing two elements (because the aforementioned list contained only one element) that are ordered. These lists are now compared to each other in a similar manner: First you select two list. In this two lists, then you select the first element of each of these lists and compare them to each other. The one that's smaller will be put in first into a new list. Then in the list that the item was just put into the new list, we select the next element and compare it with the currently selected element in the other list. Again we compare both elements and put it into the new list. We repeat this process until we only got one big list of sorted elements.
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
[java code that implements the sorting algorithm]
Heap Sort
First we have to order the unsorted list into a heap. The heap can be presented as a binary tree. But it is saved in an array. This is how you calculate the parents and the children at one point of the array:
Parent x==> child1: 2x+1; child2: 2x+2
Child y==> parent: (y-1)/2
Child y==> parent: (y-1)/2
The Heap has by definition the largest number as a root. So, in order to sort our list, we put the root element into the last place of the list. After that a new root has to be selected. We want the last Heap element to be the root. of course we have to check whether this suffice the definition of a heap, because the heap has to be the largest element. If it is not, then we will swap it with the largest child until the heap becomes consistent. From there we now have the largest element of the remaining list as a root. This element we will put into the next to last part. We will repeat this until all the heap doesn't contain any elements.
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
[pictures that illustrates the important steps]
[java code that implements the sorting algorithm]
The video of the software can be seen in this post.
If you think the algorithm aren't correcty described, please say so. I'd appreciate any improvement suggestions. Thank you in advance. :-)
No comments:
Post a Comment