Algorithm SORTING

Algorithm SORT
• Ordering the data is very important for the data type numeric or character data.
• Ordering can be done in ascending (up sequence) and descending (sequential down)
• Ordering (Sorting) is the process of reconstructing the previous data has been compiled with a certain pattern, so arranged on a regular basis according to certain rules.

Example:
Random Data: 5 6 8 1 3 25 10
Ascending: 1 3 5 6 8 10 25
Descending: 25 10 8 6 5 3 1

DECLARATION FOR SORTING ARRAYS
Declare:
int data [100];
int n; / / for the amount of data

Function for 2 Fruit Exchange Data:
public exchange (int * a, int * b) (
int t =* a;
* a =* b;
* b = t;
)

Data sorting METHOD
• Ordering by comparison (comparison-based sorting)
o Bubble Sort, Exchange Sort
• Ordering by priority (priority queue sorting method)
o Selection Sort, Heap Sort
• Ordering and maintenance based on the insertion sequence (the insert and keep sorted method)
o Insertion Sort, Tree Sort
• Ordering based on division and mastery (devide and conquer method)
o Quick Sort, Merge Sort
• Ordering less decline (diminishing increment sort method)
o Shell Sort

Bubble SORT
• The easiest sorting method but it is the slowest method.
• Given the name "Bubble" because the ordering process gradually moves / move to the right position, like the bubbles that come out of a glass of sparkling.
• Bubble Sort to sort the data by comparing the current element with the next element.
• Ordering Ascending: If the element is now larger than the next element the two elements exchanged.
• Ordering Descending: If the element is now smaller than the next element, then the two elements exchanged.
• This algorithm is like shifting one by one element from right to left or left to right, depending on the type pengurutannya.
• When a process has been completed, the bubble sort would repeat the process, and so on.
• When will it stop? Bubble sort stopped if the entire array has been checked and there is no exchange that can be done, and have achieved the desired perurutan.

Sort Buble Procedure

/ / Version 1
public bubble_sort () (
for (int i = 1; i = i; j -) (
if (data [j] data [j +1])
exchange (& data [j], & data [j +1]); / / descending
)
)
)

EXCHANGE SORT
• Very similar to the Bubble Sort
• Many are saying the same Bubble Sort Exchange Sort
• Pebedaan: in terms of how to compare elements between elements.
• Exchange sort to compare an element with other elements in the array, and exchange elements if necessary. So there is an element that has always been the central element (pivot).
• The Bubble sort will compare the first element / last with the previous elements / after, then the element before / after that it will be the center (pivot) for comparison with the previous elements / after another, and so on.

Procedur e Exchange Sort

public exchange_sort ()
(
for (int i = 0; i = 0; i -)
siftDown (numbers, i, array_size);

for (i = array_size-1; i> = 1; i -)
(
temp = numbers [0];
numbers [0] = numbers [i];
numbers [i] = temp;
New siftDown (numbers, 0, i-1);
)
)

private siftDown (int numbers [], int root, int bottom)
(
int done, maxChild, temp;

done = 0;
while ((root * 2 <= bottom) & & (! done))
(
if (root * 2 == bottom)
maxChild = root * 2;
else if (numbers [root * 2]> numbers [root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;

if (numbers [root] (
temp = numbers [root];
numbers [root] = numbers [maxChild];
numbers [maxChild] = temp;
root = maxChild;
)
else
done = 1;
)
)
)

SELECTION SORT
• It is a combination of sorting and searching
• For each process, to search for elements that have not yet sorted smallest or largest value will be exchanged into the right position in the array.
• For example, for the first round, will search the data with the smallest value and this data will be placed on the smallest index (data [0]), in the second round will be the second smallest of the data sought, and will be placed in the second index (data [1]).
• During the process, comparison and modification is only done on the comparison index alone, the physical exchange of data occurs at the end of the process.

Sort Selection Procedure

public selection_sort () (
for (int i = 0; itemp & & j> = 0) (
data [j +1] = data [j];
j -;
)
data [j +1] = temp;
)
)

MERGE SORT
• The data will be sorted and divided into 2 parts, and placed in 2 different arrays.
• Merge Sort requires 3 array, 1 array to place the results, and the rest is data to be in the listing.
• Ke-2 array is then stored in the listing on each array, and then combined in the first array.
• For example: a data, broken down into the array and array to 2-3, and then array the array to 2 and 3 do-sorting process. After getting the results, sorting the results from the array to-2 and the 3digabungkan the array to-1.

Procedure Merge Sort

class Merge (
public mergeSort (int numbers [], int temp [], int array_size)
(
New m_sort (numbers, temp, 0, array_size - 1);
)

private m_sort (int numbers [], int temp [], int left, int right)
(
int mid;

if (right> left)
(
mid = (right + left) / 2;
New m_sort (numbers, temp, left, mid);
New m_sort (numbers, temp, mid +1, right);

new merge (numbers, temp, left, mid +1, right);
)
)

private merge (int numbers [], int temp [], int left, int mid, int right)
(
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) & & (mid <= right))
(
if (numbers [left] <= numbers [mid])
(
temp [tmp_pos] = numbers [left];
tmp_pos + tmp_pos = 1;
left = left +1;
)
else
(
temp [tmp_pos] = numbers [mid];
tmp_pos + tmp_pos = 1;
mid = mid + 1;
)
)

while (left <= left_end)
(
temp [tmp_pos] = numbers [left];
left = left + 1;
tmp_pos + tmp_pos = 1;
)
while (mid <= right)
(
temp [tmp_pos] = numbers [mid];
mid = mid + 1;
tmp_pos + tmp_pos = 1;
)

for (i = 0; i <= num_elements; i + +)
(
numbers [right] = temp [right];
right = right - 1;
)
)
)

QUICK SORT
• It is a very fast method with a simple algorithm theory, but in the writing program is very difficult.
• It is a combination of methods Exchange Sort and Merge Sort method.
• There are four steps in doing this method, namely:
o If (n <= 1), then back to the beginning or mengehentikan process.
o Take one element of the array as the center (Pivot) as well as the methods Exchange Sort.
o Array is split into two parts, the first fraction consists of array elements larger than Pivot, while fractional-2 array to have a smaller element of the Pivot.
o Then, the two pieces of the sorting process.

Procedure Quick Sort

Quick Class (
public quickSort (int numbers [], int array_size)
(
New q_sort (numbers, 0, array_size - 1);
)

private q_sort (int numbers [], int left, int right)
(
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = numbers [left];
while (left (
while ((numbers [right]> = pivot) & & (left right -;
if (left! = right)
(
numbers [left] = numbers [right];
left + +;
)
while ((numbers [left] <= pivot) & & (left left + +;
if (left! = right)
(
numbers [right] = numbers [left];
right -;
)
)
numbers [left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left New q_sort (numbers, left, pivot-1);
if (right> pivot)
New q_sort (numbers, pivot +1, right);
)
)

SHELL SORT
• It is a method of O (n2) is very efficient and complex.
• Invented by Donald Shell in 1959.
• It is a form of Increment Sort method, and better known as "comb sort" in the programming world is not perfect.
• The concept is similar to Insertion Sort method.

Procedure Shell Sort

class Shell_Sort (
public shellSort (int numbers [], int array_size)
(
int i, j, increment, temp;

increment = 3;
while (increment> 0)
(
for (i = 0; i (
j = i;
temp = numbers [i];
while ((j> = increment) & & (numbers [j-increment]> temp))
(
numbers [j] = numbers [j - increment];
j = j - increment;
)
numbers [j] = temp;
)
if (increment / 2! = 0)
increment = increment / 2;
else if (increment == 1)
increment = 0;
else
increment = 1;
)
)
)