Gnome Sort
public static int[] gnomeSort(int[] nums){ //takes unsorted array, returns sorted
int index=1; //start of search
int temp;
while(index<nums.length){ //until the array is fully sorted
if(nums[index]<nums[index-1]){ //compares nums[index] with nums[index-1]. if smaller, switch.
temp=nums[index];
nums[index]=nums[index-1];
nums[index-1]=temp;
index--; //must decrease index to recheck. since they have been swapped, the array may still be out of order
if(index==0){ //prevents index from going lower than 1
index=1;
}
}
else{
index++; //if sorted, go up
}
}
return(nums); //reaching the end of the array- completely sorted, returns nums
}
Gnome Sort is one of the easiest sorting algorithms, along with bubble sort, with average speed O(n^2). It is useful for teaching as one of the easiest sorting algorithms to write and read, with only one loop needed. Basically, it goes through the array, checking adjacent elements. If a swap occurs, it must recheck the element just swapped with the one before it, to check if it needs to be swapped again, and so forth. When the loop reaches the end of the array, we know it is fully sorted, and return the sorted array.
FUN FACT: It is also known as "Stupid Sort"
Example Given an unsorted array, a = [5, 3, 2, 4], the gnome sort would take the following steps during the while loop. The "current position" is highlighted in bold:
Current array Action to take
[5, 3, 2, 4] a[pos] < a[pos-1], swap:
[3, 5, 2, 4] a[pos] >= a[pos-1], increment pos:
[3, 5, 2, 4] a[pos] < a[pos-1], swap and pos > 1, decrement pos:
[3, 2, 5, 4] a[pos] < a[pos-1], swap:
[2, 3, 5, 4] a[pos] >= a[pos-1], increment pos:
[2, 3, 5, 4] a[pos] >= a[pos-1], increment pos:
[2, 3, 5, 4] a[pos] < a[pos-1], swap and pos > 1, decrement pos:
[2, 3, 4, 5] a[pos] >= a[pos-1], increment pos:
[2, 3, 4, 5] a[pos] >= a[pos-1], increment pos:
[2, 3, 4, 5] pos == length(a), finished.
int index=1; //start of search
int temp;
while(index<nums.length){ //until the array is fully sorted
if(nums[index]<nums[index-1]){ //compares nums[index] with nums[index-1]. if smaller, switch.
temp=nums[index];
nums[index]=nums[index-1];
nums[index-1]=temp;
index--; //must decrease index to recheck. since they have been swapped, the array may still be out of order
if(index==0){ //prevents index from going lower than 1
index=1;
}
}
else{
index++; //if sorted, go up
}
}
return(nums); //reaching the end of the array- completely sorted, returns nums
}
Gnome Sort is one of the easiest sorting algorithms, along with bubble sort, with average speed O(n^2). It is useful for teaching as one of the easiest sorting algorithms to write and read, with only one loop needed. Basically, it goes through the array, checking adjacent elements. If a swap occurs, it must recheck the element just swapped with the one before it, to check if it needs to be swapped again, and so forth. When the loop reaches the end of the array, we know it is fully sorted, and return the sorted array.
FUN FACT: It is also known as "Stupid Sort"
Example Given an unsorted array, a = [5, 3, 2, 4], the gnome sort would take the following steps during the while loop. The "current position" is highlighted in bold:
Current array Action to take
[5, 3, 2, 4] a[pos] < a[pos-1], swap:
[3, 5, 2, 4] a[pos] >= a[pos-1], increment pos:
[3, 5, 2, 4] a[pos] < a[pos-1], swap and pos > 1, decrement pos:
[3, 2, 5, 4] a[pos] < a[pos-1], swap:
[2, 3, 5, 4] a[pos] >= a[pos-1], increment pos:
[2, 3, 5, 4] a[pos] >= a[pos-1], increment pos:
[2, 3, 5, 4] a[pos] < a[pos-1], swap and pos > 1, decrement pos:
[2, 3, 4, 5] a[pos] >= a[pos-1], increment pos:
[2, 3, 4, 5] a[pos] >= a[pos-1], increment pos:
[2, 3, 4, 5] pos == length(a), finished.
Provided by website-hit-counters.com site. |