Tugas algo
January 13th, 2016
Bubble Sort
Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue moon and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort is stable and adaptive.
Algorithm
- Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
- If at least one swap has been done, repeat step 1.
You can imagine that on every step big bubbles float to the surface and stay there. At the step, when no bubble moves, sorting stops. Let us see an example of sorting an array to make the idea of bubble sort clearer.
Example. Sort {5, 1, 12, -5, 16} using bubble sort.
Complexity analysis
Average and worst case complexity of bubble sort is O(n2). Also, it makes O(n2) swaps in the worst case. Bubble sort is adaptive. It means that for almost sorted array it gives O(n) estimation. Avoid implementations, which don’t check if the array is already sorted on every step (any swaps made). This check is necessary, in order to preserve adaptive property.
Turtles and rabbits
One more problem of bubble sort is that its running time badly depends on the initial order of the elements. Big elements (rabbits) go up fast, while small ones (turtles) go down very slow. This problem is solved in theCocktail sort.
Turtle example. Thought, array {2, 3, 4, 5, 1} is almost sorted, it takes O(n2) iterations to sort an array. Element {1} is a turtle.
Rabbit example. Array {6, 1, 2, 3, 4, 5} is almost sorted too, but it takes O(n) iterations to sort it. Element {6} is a rabbit. This example demonstrates adaptive property of the bubble sort.
Code snippets
There are several ways to implement the bubble sort. Notice, that “swaps” check is absolutely necessary, in order to preserve adaptive property.
Java
public void bubbleSort(int[] arr) {
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < arr.length – j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
C++
void bubbleSort(int arr[], int n) {
bool swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < n – j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
Selection Sort
Selection sort is one of the O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Selection sort is notable for its programming simplicity and it can over perform other sorts in certainsituations (see complexity analysis for more details).
Algorithm
The idea of algorithm is quite simple. Array is imaginary divided into two parts – sorted one and unsorted one. At the beginning, sorted part is empty, while unsorted one contains whole array. At every step, algorithm finds minimal element in the unsorted part and adds it to the end of the sorted one. When unsorted partbecomes empty, algorithm stops.
When algorithm sorts an array, it swaps first element of unsorted part with minimal element and then it is included to the sorted part. This implementation of selection sort in not stable. In case of linked list is sorted, and, instead of swaps, minimal element is linked to the unsorted part, selection sort is stable.
Let us see an example of sorting an array to make the idea of selection sort clearer.
Example. Sort {5, 1, 12, -5, 16, 2, 12, 14} using selection sort.
Complexity analysis
Selection sort stops, when unsorted part becomes empty. As we know, on every step number of unsorted elements decreased by one. Therefore, selection sort makes n steps (n is number of elements in array) of outer loop, before stop. Every step of outer loop requires finding minimum in unsorted part. Summing up, n + (n – 1) + (n – 2) + … + 1, results in O(n2) number of comparisons. Number of swaps may vary from zero (in case of sorted array) to n – 1 (in case array was sorted in reversed order), which results in O(n) number of swaps. Overall algorithm complexity is O(n2).
Fact, that selection sort requires n – 1 number of swaps at most, makes it very efficient in situations, when write operation is significantly more expensive, than read operation.
Code snippets
Java
public void selectionSort(int[] arr) {
int i, j, minIndex, tmp;
int n = arr.length;
for (i = 0; i < n – 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
C++
void selectionSort(int arr[], int n) {
int i, j, minIndex, tmp;
for (i = 0; i < n – 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
Insertion Sort in C++
Insertion sort is a faster and more improved sorting algorithm than selection sort. In selection sort the algorithm iterates through all of the data through every pass whether it is already sorted or not. However, insertion sort works differently, instead of iterating through all of the data after every pass the algorithm only traverses the data it needs to until the segment that is being sorted is sorted. Again there are two loops that are required by insertion sort and therefore two main variables, which in this case are named ‘i’ and ‘j’. Variables ‘i’ and ‘j’ begin on the same index after every pass of the first loop, the second loop only executes if variable ‘j’ is greater then index 0 AND arr[j] < arr[j – 1]. In other words, if ‘j’ hasn’t reached the end of the data AND the value of the index where ‘j’ is at is smaller than the value of the index to the left of ‘j’, finally ‘j’ is decremented. As long as these two conditions are met in the second loop it will keep executing, this is what sets insertion sort apart from selection sort. Only the data that needs to be sorted is sorted. As always a visual representation helps.
Algorithm for insertion sort starts here variable i begins at index 1 and j = i 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented, condition for the second loop is no longer met therefore the loop breaks back into the first loop 
i is incremented, j = i 
Conditions for the second loop are not met so no swap and j is not decremented, i is incremented and j = i 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented, condition for the second loop is no longer met therefore the loop breaks back into the first loop 
i is incremented, j = i 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented, condition for the second loop is no longer met therefore the loop breaks back into the first loop 
i is incremented, j = i 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented, condition for the second loop is no longer met therefore the loop breaks back into the first loop 
i is incremented, j = i 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented 
j > 0 AND arr[j] < arr[j-1] are both met so the algorithm jumps into the second loop which performs the swap 
j is decremented, condition for the second loop is no longer met therefore the loop breaks back into the first loop 
i is incremented, j = i, the first loops condition is no longer met so the loop breaks and the insertion sort algorithm finishes 
void insertion_sort (int arr[], int length){ int j, temp; for (int i = 0; i < length; i++){ j = i; while (j > 0 && arr[j] < arr[j-1]){ temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; j--; } } }
Quicksort
Quicksort is a fast sorting algorithm, which is used not only for educational purposes, but widely applied in practice. On the average, it has O(n log n) complexity, making quicksort suitable for sorting big data volumes. The idea of the algorithm is quite simple and once you realize it, you can write quicksort as fast as bubble sort.
Algorithm
The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:
- Choose a pivot value. We take the value of the middle element as pivot value, but it can be any value, which is in range of sorted values, even if it doesn’t present in the array.
- Partition. Rearrange elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and all elements greater than the pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Notice, that array may be divided in non-equal parts.
- Sort both parts. Apply quicksort algorithm recursively to the left and the right parts.
Partition algorithm in detail
There are two indices i and j and at the very beginning of the partition algorithm i points to the first element in the array and j points to the last one. Then algorithm moves i forward, until an element with value greater or equal to the pivot is found. Index j is moved backward, until an element with value lesser or equal to the pivot is found. If i ≤ j then they are swapped and i steps to the next position (i + 1), j steps to the previous one (j – 1). Algorithm stops, when i becomes greater than j.
After partition, all values before i-th element are less or equal than the pivot and all values after j-th element are greater or equal to the pivot.
Example. Sort {1, 12, 5, 26, 7, 14, 3, 7, 2} using quicksort.
Notice, that we show here only the first recursion step, in order not to make example too long. But, in fact, {1, 2, 5, 7, 3} and {14, 7, 26, 12} are sorted then recursively.
Why does it work?
On the partition step algorithm divides the array into two parts and every element a from the left part is less or equal than every element b from the right part. Also a and b satisfy a ≤ pivot ≤ b inequality. After completion of the recursion calls both of the parts become sorted and, taking into account arguments stated above, the whole array is sorted.
Complexity analysis
On the average quicksort has O(n log n) complexity, but strong proof of this fact is not trivial and not presented here. Still, you can find the proof in [1]. In worst case, quicksort runs O(n2) time, but on the most “practical” data it works just fine and outperforms other O(n log n) sorting algorithms.
Code snippets
Partition algorithm is important per se, therefore it may be carried out as a separate function. The code for C++ contains solid function for quicksort, but Java code contains two separate functions for partition and sort, accordingly.
Java
int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j–;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j–;
}
};
return i;
}
void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index – 1)
quickSort(arr, left, index – 1);
if (index < right)
quickSort(arr, index, right);
}
C++
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j–;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j–;
}
};
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
Merge Sort
You start with an unordered sequence. You create N empty queues. You loop over every item to be sorted. On each loop iteration, you look at the last element in the key. You move that item into the end of the queue which corresponds to that element. When you are finished looping you concatenate all the queues together into another sequence. You then reapply the procedure described but look at the second last element in the key. You keep doing this until you have looped over every key. When you complete this process the resulting sequence will be sorted as described above.
Key Comparing[edit]
Keys are compared in the following way: Let ka be the key of the one item, called item A, let kb be the key of the other item, called item B. Let ka(i) be the ith entry in the key ka, where the first entry is at index 0. Let i = 0. If the keys are less than i elements long then the keys are equal. If ka(i) < kb(i), then item A is ordered before item B. If ka(i) > kb(i), then item B is ordered before item A. If ka(i) = kb(i), then add one to i, and return the line under “Let i = 0.”
Time Cost
Let ni be the number of items in the sequence to be sorted. N is number of integers that each key element can take. Let nk be the number of keys in each item.
The total time to sort the sequence is thus O(nk(ni + N)).
Common Lisp
Naive implementation, translation of pseudocode found at Wikipedia.
(defmacro
apenda-primeiro (ret1 left1)
"Appends first element of left1 to right1, and removes first element from left1."
`(progn
(setf ,ret1 (if (eq ,ret1 nil) (cons (car ,left1) nil) (append ,ret1 (cons (car ,left1) nil))))
(setf ,left1 (cdr ,left1))))
(defun
merge-func (left right)
"Our very own merge function, takes two lists, left and right, as arguments, and returns a new merged list."
(let (ret)
(loop
(if (or (not (null left)) (not (null right)))
(progn
(if (and (not (null left)) (not (null right)))
(if (<= (car left) (car right))
(apenda-primeiro ret left)
(apenda-primeiro ret right))
(if (not (null left))
(apenda-primeiro ret left)
(if (not (null right))
(apenda-primeiro ret right)))))
(return)))
ret))
(defun
merge-sort (m)
"Merge-sort proper. Takes a list m as input and returns a new, sorted list; doesn't touch the input."
(let* ((tam (length m))
(mid (ceiling (/ tam 2)))
(left)
(right))
(if (<= tam 1)
m
(progn
(loop for n from 0 to (- mid 1) do
(apenda-primeiro left m))
(loop for n from mid to (- tam 1) do
(apenda-primeiro right m))
(setf left (merge-sort left))
(setf right (merge-sort right))
(merge-func left right)))))
Simpler Implementation in a somewhat more functional style.
(defun sort-func (frst scond &optional (sorted nil))
"Sorts the elements from the first and second list in ascending order and puts them in `sorted`"
(cond ((and (null frst) (null scond)) sorted)
((null frst) (append (reverse sorted) scond))
((null scond) (append (reverse sorted) frst))
(t (let ((x (first frst))
(y (first scond)))
(if (< x y)
(sort-func (rest frst) scond (push x sorted))
(sort-func frst (rest scond) (push y sorted)))))))
(defun merge-sort (lst)
"Divides the elements in `lst` into individual elements and sorts them"
(when (not (null lst))
(let ((divided (mapcar #'(lambda (x) (list x)) lst)))
(labels ((merge-func (div-list &optional (combined '())) ; merges the elements in ascending order
(if div-list
(merge-func (rest (rest div-list)) (push (sort-func (first div-list) (second div-list)) combined))
combined))
(final-merge (div-list) ; runs merge-func until all elements have been reconciled
(if (> (length div-list) 1)
(final-merge (merge-func div-list))
div-list)))
(final-merge divided)))))
C
///function:
mergeSort(name_array);
//tipo Data used:
typedef struct data{
char*some;
int data;
} DATA;
typedef struct _nodo{
int key;
DATA data;
}nodo;
///n is kept as global
int n;
void merge(nodo*a,nodo*aux,int left,int right,int rightEnd){
int i,num,temp,leftEnd=right-1;
temp=left;
num=rightEnd-left+1;
while((left<=leftEnd)&&(right<=rightEnd)){
if(a[left].key<=a[right].key){
aux[temp++]=a[left++];
}
else{
aux[temp++]=a[right++];
}
}
while(left<=leftEnd){
aux[temp++]=a[left++];
}
while(right<=rightEnd){
aux[temp++]=a[right++];
}
for (i=1;i<=num;i++,rightEnd--){
a[rightEnd]=aux[rightEnd];
}
}
void mSort(nodo*a,nodo*aux,int left,int right){
int center;
if (left<right){
center=(left+right)/2;
mSort(a,aux,left,center);
mSort(a,aux,center+1,right);
merge(a,aux,left,center+1,right);
}
}
void mergeSort(nodo*p){
nodo*temp=(nodo*)malloc(sizeof(nodo)*n);
mSort(p,temp,0,n-1);
free(temp);
}
Fortran
subroutine Merge(A,NA,B,NB,C,NC)
integer, intent(in) :: NA,NB,NC ! Normal usage: NA+NB = NC
integer, intent(in out) :: A(NA) ! B overlays C(NA+1:NC)
integer, intent(in) :: B(NB)
integer, intent(in out) :: C(NC)
integer :: I,J,K
I = 1; J = 1; K = 1;
do while(I <= NA .and. J <= NB)
if (A(I) <= B(J)) then
C(K) = A(I)
I = I+1
else
C(K) = B(J)
J = J+1
endif
K = K + 1
enddo
do while (I <= NA)
C(K) = A(I)
I = I + 1
K = K + 1
enddo
return
end subroutine merge
recursive subroutine MergeSort(A,N,T)
integer, intent(in) :: N
integer, dimension(N), intent(in out) :: A
integer, dimension((N+1)/2), intent (out) :: T
integer :: NA,NB,V
if (N < 2) return
if (N == 2) then
if (A(1) > A(2)) then
V = A(1)
A(1) = A(2)
A(2) = V
endif
return
endif
NA=(N+1)/2
NB=N-NA
call MergeSort(A,NA,T)
call MergeSort(A(NA+1),NB,T)
if (A(NA) > A(NA+1)) then
T(1:NA)=A(1:NA)
call Merge(T,NA,A(NA+1),NB,A,N)
endif
return
end subroutine MergeSort
program TestMergeSort
integer, parameter :: N = 8
integer, dimension(N) :: A = (/ 1, 5, 2, 7, 3, 9, 4, 6 /)
integer, dimension ((N+1)/2) :: T
call MergeSort(A,N,T)
write(*,'(A,/,10I3)')'Sorted array :',A
end program TestMergeSort
Scheme
(define (mergesort x)
(if (= 0 (length x))
'()
;else
(if (= (length x) 1)
x
;else
(combine (mergesort (firstHalf x (/ (length x) 2))) (mergesort (lastHalf x (/ (length x) 2)))
)
)
)
)
(define (combine list1 list2)
(if (null? list1) list2
;else
(if (null? list2) list1
;else
(if (<= (car list1) (car list2))
;car of list 1 is second element of list 2
(cons (car list1) (combine (cdr list1) list2))
;else
(cons (car list2) (combine list1 (cdr list2)))
)
)
)
)
(define (firstHalf L N)
(if (= N 0)
null
)
(if (or (= N 1) (< N 2))
(list (car L))
;else
(cons (car L) (firstHalf (cdr L) (- N 1)))))
(define (lastHalf L N)
(if (= N 0) L); Base Case
(if (or (= N 1) (< N 2))
(cdr L)
;else
(lastHalf (cdr L) (- N 1)))
)
Haskell
sort :: Ord a => [a] -> [a]
sort [] = []
sort [x] = [x]
sort xs = merge (sort ys) (sort zs)
where
(ys,zs) = splitAt (length xs `div` 2) xs
merge [] y=y
merge x []=x
merge (x:xs) (y:ys)
| x<=y = x:merge xs (y:ys)
| otherwise = y:merge (x:xs) ys
A slightly more efficient version only traverses the input list once to split (note that length takes linear time in Haskell):
sort :: Ord a => [a] -> [a]
sort [] = []
sort [x] = [x]
sort xs = merge (sort ys) (sort zs)
where (ys,zs) = split xs
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x<=y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
split [] = ([], [])
split [x] = ([x], [])
split (x:y:xs) = (x:l, y:r)
where (l, r) = split xs
Prolog
This is an ISO-Prolog compatible implementation of merge sort.
mergesort(L, Sorted) :-
once(mergesort_r(L, Sorted)).
mergesort_r([], []).
mergesort_r([X], [X]).
mergesort_r(L, Sorted) :-
split(L, Left, Right),
mergesort_r(Left, SortedL),
mergesort_r(Right, SortedR),
merge(SortedL, SortedR, Sorted).
% Split list into two roughly equal-sized lists.
split([], [], []).
split([X], [X], []).
split([X,Y|Xs], [X|Left], [Y|Right]) :-
split(Xs, Left, Right).
% Merge two sorted lists into one.
merge(Left, [], Left).
merge([], Right, Right).
merge([X|Left], [Y|Right], [Z|Merged]) :-
(X @< Y ->
Z = X,
merge(Left, [Y|Right], Merged)
;
Z = Y,
merge([X|Left], Right, Merged)
).
Python
A “standard” mergesort:
from heapq import merge
def mergesort(w):
"""Sort list w and return it."""
if len(w)<2:
return w
else:
mid=len(w)//2
# sort the two halves of list w recursively with mergesort and merge them
return merge(mergesort(w[:mid]), mergesort(w[mid:]))
An alternative method, using a recursive algorithm to perform the merging in place (except for the O(log n) overhead to trace the recursion) in O(n log n) time:
def merge(lst, frm, pivot, to, len1, len2):
if len1==0 or len2==0: return
if len1+len2 == 2:
if lst([pivot])<lst[frm]: lst[pivot], lst[frm] = lst[frm], lst[pivot]
return
if len1 > len2:
len11 = len1/2
firstcut, secondcut, length = frm+len11, pivot, to-pivot
while length > 0:
half = length/2
mid = secondcut+half
if lst[mid]<lst[firstcut]: secondcut, length = mid+1, length-half-1
else: length = half
len22 = secondcut - pivot
else:
len22 = len2/2
firstcut, secondcut, length = frm, pivot+len22, pivot-frm
while length > 0:
half = length/2
mid = firstcut+half
if lst[secondcut]<lst[mid]: length = half
else: firstcut, length = mid+1, length-half-1
len11 = firstcut-frm
if firstcut!=pivot and pivot!=secondcut:
n, m = secondcut-firstcut, pivot-firstcut
while m != 0: n, m = m, n%m
while n != 0:
n -= 1
p1, p2 = firstcut+n, n+pivot
val, shift = lst[p1], p2-p1
while p2 != firstcut+n:
lst[p1], p1 = lst[p2], p2
if secondcut-p2>shift: p2 += shift
else: p2 = pivot-secondcut+p2
lst[p1] = val
newmid = firstcut+len22
merge(lst, frm, firstcut, newmid, len11, len22)
merge(lst, newmid, secondcut, to, len1-len11, len2-len22)
def sort(lst, frm=0, to=None):
if to is None: to = len(lst)
if to-frm<2: return
middle = (frm+to)/2
sort(lst, frm, middle)
sort(lst, middle, to)
merge(lst, frm, middle, to, middle-frm, to-middle)
Ruby
def merge_sort(array)
return array if array.size <= 1
left = merge_sort array[0, array.size / 2]
right = merge_sort array[array.size / 2, array.size]
merge(left, right)
end
def merge(left, right)
result = []
while left.size > 0 && right.size > 0
result << if left[0] <= right[0]
left.shift
else
right.shift
end
end
result.concat(left).concat(right)
end
Miranda
sort [] = []
sort [x] = [x]
sort array = merge (sort left) (sort right)
where
left = [array!y | y <- [0..mid]]
right = [array!y | y <- [(mid+1)..max]]
max = #array - 1
mid = max div 2
Standard ML
fun mergesort [] = []
| mergesort [x] = [x]
| mergesort lst =
let fun merge ([],ys) = ys (*merges two sorted lists to form a sorted list *)
| merge (xs,[]) = xs
| merge (x::xs,y::ys) =
if x<y then
x::merge (xs,y::ys)
else
y::merge (x::xs,ys)
;
val half = length(lst) div 2;
in
merge (mergesort (List.take (lst, half)),mergesort (List.drop (lst, half)))
end
;
Java[edit]
public int[] mergeSort(int array[])
// pre: array is full, all elements are valid integers (not null)
// post: array is sorted in ascending order (lowest to highest)
{
// if the array has more than 1 element, we need to split it and merge the sorted halves
if(array.length > 1)
{
// number of elements in sub-array 1
// if odd, sub-array 1 has the smaller half of the elements
// e.g. if 7 elements total, sub-array 1 will have 3, and sub-array 2 will have 4
int elementsInA1 = array.length / 2;
// we initialize the length of sub-array 2 to
// equal the total length minus the length of sub-array 1
int elementsInA2 = array.length - elementsInA1;
// declare and initialize the two arrays once we've determined their sizes
int arr1[] = new int[elementsInA1];
int arr2[] = new int[elementsInA2];
// copy the first part of 'array' into 'arr1', causing arr1 to become full
for(int i = 0; i < elementsInA1; i++)
arr1[i] = array[i];
// copy the remaining elements of 'array' into 'arr2', causing arr2 to become full
for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
arr2[i - elementsInA1] = array[i];
// recursively call mergeSort on each of the two sub-arrays that we've just created
// note: when mergeSort returns, arr1 and arr2 will both be sorted!
// it's not magic, the merging is done below, that's how mergesort works :)
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
// the three variables below are indexes that we'll need for merging
// [i] stores the index of the main array. it will be used to let us
// know where to place the smallest element from the two sub-arrays.
// [j] stores the index of which element from arr1 is currently being compared
// [k] stores the index of which element from arr2 is currently being compared
int i = 0, j = 0, k = 0;
// the below loop will run until one of the sub-arrays becomes empty
// in my implementation, it means until the index equals the length of the sub-array
while(arr1.length != j && arr2.length != k)
{
// if the current element of arr1 is less than current element of arr2
if(arr1[j] < arr2[k])
{
// copy the current element of arr1 into the final array
array[i] = arr1[j];
// increase the index of the final array to avoid replacing the element
// which we've just added
i++;
// increase the index of arr1 to avoid comparing the element
// which we've just added
j++;
}
// if the current element of arr2 is less than current element of arr1
else
{
// copy the current element of arr2 into the final array
array[i] = arr2[k];
// increase the index of the final array to avoid replacing the element
// which we've just added
i++;
// increase the index of arr2 to avoid comparing the element
// which we've just added
k++;
}
}
// at this point, one of the sub-arrays has been exhausted and there are no more
// elements in it to compare. this means that all the elements in the remaining
// array are the highest (and sorted), so it's safe to copy them all into the
// final array.
while(arr1.length != j)
{
array[i] = arr1[j];
i++;
j++;
}
while(arr2.length != k)
{
array[i] = arr2[k];
i++;
k++;
}
}
// return the sorted array to the caller of the function
return array;
}
JavaScript[edit]
;(function() {
var defaultComparator = function (a, b) {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
}
Array.prototype.mergeSort = function( comparator ) {
var i, j, k,
firstHalf,
secondHalf,
arr1,
arr2;
if (typeof comparator != "function") { comparator = defaultComparator; }
if (this.length > 1) {
firstHalf = Math.floor(this.length / 2);
secondHalf = this.length - firstHalf;
arr1 = [];
arr2 = [];
for (i = 0; i < firstHalf; i++) {
arr1[i] = this[i];
}
for(i = firstHalf; i < firstHalf + secondHalf; i++) {
arr2[i - firstHalf] = this[i];
}
arr1.mergeSort( comparator );
arr2.mergeSort( comparator );
i=j=k=0;
while(arr1.length != j && arr2.length != k) {
if ( comparator( arr1[j], arr2[k] ) <= 0 ) {
this[i] = arr1[j];
i++;
j++;
}
else {
this[i] = arr2[k];
i++;
k++;
}
}
while (arr1.length != j) {
this[i] = arr1[j];
i++;
j++;
}
while (arr2.length != k) {
this[i] = arr2[k];
i++;
k++;
}
}
}
})();
Separate into two functions:
function mergesort(list){
if (list.length <= 1)
return list;
var mid = Math.floor(list.length / 2),
left = list.slice(0, mid),
right = list.slice(mid, list.length);
return merge(mergesort(left), mergesort(right))
}
function merge(left, right){
var sorted = [];
while (left && left.length > 0 && right && right.length > 0){
sorted.push(left[0] <= right[0]? left.shift() : right.shift());
}
return sorted.concat(left, right);
}
C++[edit]
Here is a recursive implementation of the merge sort using STL vectors (This is a naive implementation):
//! \brief Performs a recursive merge sort on the given vector
//! \param vec The vector to be sorted using the merge sort
//! \return The sorted resultant vector after merge sort is
//! complete.
vector<int> merge_sort(vector<int>& vec)
{
// Termination condition: List is completely sorted if it
// only contains a single element.
if(vec.size() == 1)
{
return vec;
}
// Determine the location of the middle element in the vector
std::vector<int>::iterator middle = vec.begin() + (vec.size() / 2);
vector<int> left(vec.begin(), middle);
vector<int> right(middle, vec.end());
// Perform a merge sort on the two smaller vectors
left = merge_sort(left);
right = merge_sort(right);
return merge(vec,left, right);
}
And here is the implementation of the merge function:
//! \brief Merges two sorted vectors into one sorted vector
//! \param left A sorted vector of integers
//! \param right A sorted vector of integers
//! \return A sorted vector that is the result of merging two sorted
//! vectors.
vector<int> merge(vector<int> &vec,const vector<int>& left, const vector<int>& right)
{
// Fill the resultant vector with sorted results from both vectors
vector<int> result;
unsigned left_it = 0, right_it = 0;
while(left_it < left.size() && right_it < right.size())
{
// If the left value is smaller than the right it goes next
// into the resultant vector
if(left[left_it] < right[right_it])
{
result.push_back(left[left_it]);
left_it++;
}
else
{
result.push_back(right[right_it]);
right_it++;
}
}
// Push the remaining data from both vectors onto the resultant
while(left_it < left.size())
{
result.push_back(left[left_it]);
left_it++;
}
while(right_it < right.size())
{
result.push_back(right[right_it]);
right_it++;
}
//show merge process..
int i;
for(i=0;i<result.size();i++)
{
cout<<result[i]<<" ";
}
// break each line for display purposes..
cout<<"***********"<<endl;
//take a source vector and parse the result to it. then return it.
vec = result;
return vec;
}
Here’s another recursive implementation of the mergesort using arrays of variable length
#include <iostream>
using namespace std;
void merge(int a[], const int low, const int mid, const int high)
{
// Variables declaration.
int * b = new int[high+1-low];
int h,i,j,k;
h=low;
i=0;
j=mid+1;
// Merges the two array's into b[] until the first one is finish
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
// Completes the array filling in it the missing values
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
// Prints into the original array
for(k=0;k<=high-low;k++)
{
a[k+low]=b[k];
}
delete[] b;
}
void merge_sort( int a[], const int low, const int high ) // Recursive sort ...
{
int mid;
if( low < high )
{
mid = ( low + high ) / 2;
merge_sort( a, low, mid );
merge_sort( a, mid + 1, high );
merge( a, low, mid, high );
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int arraySize;
// a[] is the array to be sorted. ArraySize is the size of a[] ...
merge_sort(a, 0, (arraySize-1) ); // would be more natural to use merge_sort(a, 0, arraySize ), so please try ;-)
// some work
return 0;
}
Perl[edit]
use sort '_mergesort';
sort @array;
PHP[edit]
function merge_sort(array $left, array $right) {
$result = [];
while (count($left) && count($right)) {
if ($left[0] < $right[0]) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
return array_merge($result, $left, $right);
}
function merge(array $arrayToSort) {
if (count($arrayToSort) == 1) {
return $arrayToSort;
}
$left = merge(array_slice($arrayToSort, 0, count($arrayToSort) / 2));
$right = merge(array_slice($arrayToSort, count($arrayToSort) / 2, count($arrayToSort)));
return merge_sort($left, $right);
}
/**
* Not sorted array, should be split in two chunks and sort them (possible with the same algorithm, but not always)
*/
print_r(merge([7, 1, 8, 9, 10, 4, 2, 5, 6, 0, 3, 25]));
/**
* Already sorted two chunks
*/
$first = [1, 2, 5, 7, 8 ,10];
$second = [3, 4, 6, 12, 15];
print_r(merge_sort($first, $second));
Groovy[edit]
def mergeSort(def list){
if (list.size() <= 1) { return list }
else {
center = list.size() / 2
left = list[0..center]
right = list[center..list.size() - 1]
merge(mergeSort(left), mergeSort(right))
}
}
def merge(def left, def right){
def sorted = []
while(left.size() > 0 || right.size() > 0)
if(left.get(0) <= right.get(0)){
sorted << left
}else{
sorted << right
}
sorted = sorted + left + right
return sorted
}
Eiffel[edit]
class
APPLICATION
create
make
feature -- Initialization
make is
--
do
end
feature -- Algorithm
mergesort(a:ARRAY[INTEGER]; l,r:INTEGER) is
-- Recursive mergesort
local
m: INTEGER
do
if l<r then
m := (l+r)//2
mergesort(a,l, m)
mergesort(a,m+1,r)
merge(a,l,m,r)
end
end
feature -- Utility feature
merge(a:ARRAY[INTEGER]; l,m,r: INTEGER) is
-- The merge feature of all mergesort variants
local
b: ARRAY[INTEGER]
h,i,j,k: INTEGER
do
i := l
j := m+1
k := l
create b.make (l, r)
from
until
i > m or j > r
loop
-- begins the merge and copies it into an array "b"
if a.item (i) <= a.item (j) then
b.item (k) := a.item (i)
i := i +1
elseif a.item (i) > a.item (j) then
b.item (k) := a.item (j)
j := j+1
end
k := k+1
end
-- Finishes the copy of the uncopied part of the array
if i > m then
from
h := j
until
h > r
loop
b.item (k+h-j) := a.item (h)
h := h+1
end
elseif j > m then
from
h := i
until
h > m
loop
b.item (k+h-i) := a.item (h)
h := h+1
end
end
-- "begins the copy to the real array"
from
h := l
until
h > r
loop
a.item (h) := b.item (h)
h := h+1
end
end
linear search itu katanya basic search, jadi proses pencarian yang paling dasar gitu lah kira-kira. Linear search juga sama kayak sequential search. Ini salah satu syntax nya.
Set i to n.
Repeat this loop:
If i ≤ 0, then exit the loop.
If A[i] = x, then exit the loop.
Set i to i − 1.
Return i.
Binary search adalah sebuah algoritma pencarian dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian untuk menemukan nilai tertentu dalam sebuah larik (array) linear. Untuk syntax contohnya seperti ini:
- Algorithm:
- n : total record of array x.
- left=0, right= n-1.
- mid =(int) (left + right)/2.
- If x[mid]=key then index = mid. Finished.
- If x[mid]<key then left = mid+1.
- If x[mid]>key then right=mid-1.
- If left £ right and x[mid] ¹ key, then repeat point 3.
- If x[mid] ¹ key then index = -1. Finished.
Interpolation Search adalah sebuah algoritma atau metode untuk mencari nilai key yang diberikan dalam array diindeks yang telah diperintahkan oleh nilai – nilai kunci. Metode ini didasari pada proses pencarian nomor telepon pada buku telepon yang mana manusia mencari melalui dengan nilai kunci yang terdapat pada buku. Teknik searching ini dilakukan dengan perkiraan letak data. Algoritmanya seperti ini:
1.In the interpolation search, we’ll split the data according to the following formula:
mid = low + (key - arr[low]) * ((high - low) / ( arr[high] - arr[low])) ;
2.If data[mid] = sought data, data has been found, searching is stopped and return mid.
3.If data[mid]!= sought data, repeat point **
4.**Searching is continued while sought data > data[min] and sought data < data[max].
arrays dan pointers
November 4th, 2015
Array merupakan koleksi data dimana setiap elemen memakai nama dan tipe yang sama serta setiap elemen diakses dengan membedakan indeks array-nya. Berikut adalah contoh variable bernama c yang mempunyai lokasi memori yang semuanya bertipe int.
C[0] = -45;
C[1] = 6;
C[2] = 0;
C[3] = 72;
C[4] = 1543;
C[5] = 43;
C[6] = 4;
Masing-masing nilai dalam setiap lokasi mempunyai identitas berupa nama c dan nomor indeks yang dituliskan di dalam tanda kurung ‘[..]’. sebagai contoh, 72 adalah nilai dari c[3].
Deklarasi Array
Variable array dideklarasikan dengan mencantumkan tipe dan nama variable yang diikuti dengan banyaknya lokasi memori yang ingin dibuat. Dengan demikian, deklarasi untuk variable array c di atas adalah :
int c[7];
Perlu diperhatikan bahwa C++ secara otomatis menyediakan lokasi memori yang sesuai dengan yang dideklarasikan, dimana nomor indeks selalu dimulai dari 0. Nilai suatu variable array dapat juga diinisialisasi secara langsung pada saat deklarasi, misalnya;
Int c[7] = {-45, 0, 6, 72, 1543, 43, 4}
Berarti setiap lokasi memori dari variable array c langsung diisi dengan nilai-nilai yang dituliskan didalam tanda kurung kurawal.
Banyaknya lokasi memori dapat secara otomatis disediakan sesuai degan banyaknya nilai yang akan dimasukkan, seperti contoh berikut yang tentunya membuat variable array dengan 10 lokasi memori:
Int x []={10, 15 12, 5, 13, 9, 6, 17, 25, 31};
Untuk memperjelas gambaran anda tentang array perhatikan contoh aplikasi variable array, yaitu program untuk menghitung jumlah setiap elemen dalam suatu array.
Sebagai gambaran dari program tersebut, dapat dibuat sebuah algoritma sebagai berikut:
1. Tentukan elemen array sebanyak yang diinginkan (dalam hal ini, elemen array tersebut berjumlah 12 buah)
2. Tentukan nilai awal indeks, batas akhir indeks dan kenaikannya (dalam hal ini, nilai awal indeks adalah 0, batas akhir indeks adalah jumlah elemen array diatas yaitu 12 dikurangi dengan 1, kenaikannya adalah 1)
3. Lakukan perulangan sesuai dengan langkah 2
4. Lakukan penjumlahan masing-masing elemen array sampai batas akhir indeks terpenuhi
5. Tampilkan penjumlahan semua elemen array
6. Selesai.
contoh Program sebagai berikut .
#include
#include
main()
{
int a[5]={10,15,20,25,30};
int b[5]={10,20};
int c[5]={15,0,30};
int j;
// Menampilkan nilai dari element array
cout<<endl;
for(j=0;j<5;j++)
{
cout<<"A ["<<j<<"] = "<<a[j]<<" , B ["<<j<<"] = "<<b[j]<<" , C ["<<j<<"] = "<<c[j]<<endl;
}
getch();
}
Pengertian Tentang Pointer. Pointer adalah suatu variabel khusus yang berisikan alamat memori dari suatu data, tidak berisikan data itu sendiri. icemaker repair marietta . Pointer sangat sering digunakan dalam program-program bahasa C, karena dapat memberikan efisiensi dalam program.
Jadi, untuk mendeklarasikan sebuah pointer xp yang menunjuk ke alamat data integer, digunakan perintah sebagai berikut:
int *xp
Terdapat dua buah operator unary yang digunakan untuk mengakses sebuah pointer, yaitu operator & dan operator * . Operator & digunakan untuk mengakses alamat data yang ditunjuk oleh pointer, sementara operator * digunakan untuk mengakses data yang alamatnya ditunjuk oleh pointer.
a = &x; /* a berisikan alamat yang ditunjuk pointer x */
b = *x; /* a berisi data yang alamatnya ditunjuk x */
Contoh program pointer
#include "iostream.h"
Void main(void)
{
int v = 7, *p;
p = &v;
cout << "Nilai v = " << v << " dan *p = " << *p
<< " \nAlamatnya = " << p << 'n';
}
Hasil dari program adalah sebagai berikut :
Nilai v = 7 dan *p = 7
Alamatnya = efffb24
Penjelasan :
Dari program pointer1, pointer p menunjukkan isi dari variabel v yaitu 7 dan alamat dari pointer adalah efffb24
Operator Pointer
Ada beberapa operator yang digunakan dalam pointer yaitu operator alamat (&)
Contoh :
int y = 5;
int *yPtr;
Maka pernyataan
yPtr = &y;
Mengandung arti bahwa alamat dari variabel y ditujukan kepada variabel pointer yPtr.
Contoh program operator pointer :
#include "iostream.h"
Int main()
{
int *ptr, num; // 1
ptr = # // 2
*ptr = 100; // 3
cout << num << " ";
(*ptr)++; // 4
cout << num << " ";
(*ptr)*2; // 5
cout << num << "\n ";
return 0;
}
Bila dijalankan hasilnya adalah sebagai berikut :
100 101 101
rangkuman algoritma
October 7th, 2015
1. Algoritma adalah prosedur untuk memecahkan masalah dalam hal tindakan yang akan dieksekusi, dan urutan di mana tindakan ini akan dieksekusi.
2. Berasal dari algoris kata dan ritmis.
3. Algoritma diperkenalkan oleh Al-Khowarizmi.
4. Dalam domain pemrograman, algoritma mendefinisikan sebagai metode yang terdiri dari langkah-langkah terstruktur dalam pemecahan masalah dengan menggunakan komputer.
4
first post
September 28th, 2015
Pengalaman selama FEP, GO, AO….. sangatlah menyenangkan. Karena selama kegiatan tersebut, saya bisa mendapatkan teman baru, skill, dll.
Hello world!
September 28th, 2015
Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂