# מיון בועות

## #C

```int[] arr = {800,11,50,771,649,770,240, 9};

int temp = 0;

for (int write = 0; write < arr.Length; write++)
{
for (int sort = 0; sort < arr.Length - 1; sort++)
{
if (arr[sort] > arr[sort + 1])
{
temp = arr[sort + 1];
arr[sort + 1] = arr[sort];
arr[sort] = temp;
}
}
Console.Write("{0} ", arr[write]);
}
```

## ++C

```/* C++ Program - Bubble Sort */

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int n, i, arr[50], j, temp;
cout<<"Enter total number of elements :";
cin>>n;
cout<<"Enter "<<n<<" numbers :";
for(i=0; i<n; i++)
{
cin>>arr[i];
}
cout<<"Sorting array using bubble sort technique...\n";
for(i=0; i<(n-1); i++)
{
for(j=0; j<(n-i-1); j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
cout<<"Elements sorted successfully..!!\n";
cout<<"Sorted list in ascending order :\n";
for(i=0; i<n; i++)
{
cout<<arr[i]<<" ";
}
getch();
}

```

## java

```public class BubbleSortExample {
static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}

}
}

}
public static void main(String[] args) {
int arr[] ={3,60,35,2,45,320,5};

System.out.println("Array Before Bubble Sort");
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
System.out.println();

bubbleSort(arr);//sorting array elements using bubble sort

System.out.println("Array After Bubble Sort");
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}

}
}

```

## python

```def bubbleSort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(ali
```

## assembly

```
.data
str1: .asciiz "ENTER VALUE"
str2: .asciiz "ENTER OP CODE"
str3: .asciiz "ERROR"
.text
li \$t6,0xffffffff       # number for errors exeption
li \$s1, '+'         # operator +
li \$s2, '-'     # operator -
li \$s3, '*'     # operator *
li \$s4, '@'     # operator @ (for end the clculation)
li \$t0,0
li \$v0,4            # code for print
syscall             # pirnt "ENTER VALUE"
li \$v0,5
syscall             # cin >> int
loop:
li \$v0,4            # code for print
la \$a0 ,str2
syscall             # pirnt "ENTER OP CODE"
li \$v0,12
syscall             # cin >> char
add \$t3,\$0 \$v0      # to keep the operator
beq \$t3,\$s4,finish  # if the operator is @ finish
li \$v0,4            # code for print
syscall             # pirnt "ENTER VALUE"
li \$v0,5            # cin int
syscall
beq \$t3,\$s2,sub_    # if the operator is '-'
beq \$t3,\$s1,add_    # if the operator is '+'
beq \$t3,\$s3,multi_  # if the operator is '*'
j loop
sub_:
sub \$t0 ,\$t0, \$v0
j loop
multi_:
mult \$t0,\$v0
mflo \$t0

mfhi \$t5                 #  \$t5 = hi
bltz \$t0,chak            # if result < 0 go to chac
bne \$t5,\$0  Error        # if result > 0
chak:
bne \$t5,\$t6 ,Error       # if \$t5 (hi) != 11111111111..11  go to error
j loop
finish:
li \$v0,1
syscall
j sof                   # if no errors skip the error messege
Error:
li \$v0,4                # code for print
la \$a0 ,str3
syscall                 # pirnt "ERROR"
li \$v0,12
syscall
sof:
end:

```

## prolog

```Domains
list = integer*.

Predicates
bubblesort(list,list).
swap(list,list).
printlist(list).

Clauses
bubblesort(InputList,SortList) :-
swap(InputList,List) , ! ,
printlist(List),
bubblesort(List,SortList).
bubblesort(SortList,SortList).

swap([X,Y|List],[Y,X|List]) :- X > Y.
swap([Z|List],[Z|List1]) :- swap(List,List1).

printlist([]) :- nl.
printlist(List).

Output :

Goal: bubblesort([2,3,1,4],L).
2 1 3 4
1 2 3 4
L=[1,2,3,4]
1 Solution

Goal: bubblesort([2,4,1,3,5,9,6],L).
2 1 4 3 5 9 6
1 2 4 3 5 9 6
1 2 3 4 5 9 6
1 2 3 4 5 6 9
L=[1,2,3,4,5,6,9]
1 Solution

```

# מיון מהיר

## ++C

```
#include <iostream>

using namespace std;

void quick_sort(int[],int,int);
int partition(int[],int,int);

int main()
{
int a[50],n,i;
cout<<"How many elements?";
cin>>n;
cout<<"\nEnter array elements:";

for(i=0;i<n;i++)
cin>>a[i];

quick_sort(a,0,n-1);
cout<<"\nArray after sorting:";

for(i=0;i<n;i++)
cout<<a[i]<<" ";

return 0;
}

void quick_sort(int a[],int l,int u)
{
int j;
if(l<u)
{
j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
}
}

int partition(int a[],int l,int u)
{
int v,i,j,temp;
v=a[l];
i=l;
j=u+1;

do
{
do
i++;

while(a[i]<v&&i<=u);

do
j--;
while(v<a[j]);

if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);

a[l]=a[j];
a[j]=v;

return(j);
}

```

## C#

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Quicksort
{
class Program
{
static void Main(string[] args)
{
// Create an unsorted array of string elements
string[] unsorted = { "z","e","x","c","m","q","a"};

// Print the unsorted array
for (int i = 0; i < unsorted.Length; i++)
{
Console.Write(unsorted[i] + " ");
}

Console.WriteLine();

// Sort the array
Quicksort(unsorted, 0, unsorted.Length - 1);

// Print the sorted array
for (int i = 0; i < unsorted.Length; i++)
{
Console.Write(unsorted[i] + " ");
}

Console.WriteLine();

}

public static void Quicksort(IComparable[] elements, int left, int right)
{
int i = left, j = right;
IComparable pivot = elements[(left + right) / 2];

while (i <= j)
{
while (elements[i].CompareTo(pivot) < 0)
{
i++;
}

while (elements[j].CompareTo(pivot) > 0)
{
j--;
}

if (i <= j)
{
// Swap
IComparable tmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;

i++;
j--;
}
}

// Recursive calls
if (left < j)
{
Quicksort(elements, left, j);
}

if (i < right)
{
Quicksort(elements, i, right);
}
}

}
}

```

## java

```
package com.java2novice.sorting;

public class MyQuickSort {

private int array[];
private int length;

public void sort(int[] inputArr) {

if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}

private void quickSort(int lowerIndex, int higherIndex) {

int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}

private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

public static void main(String a[]){

MyQuickSort sorter = new MyQuickSort();
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
```

## prolog

```quicksort([X|Xs],Ys) :-
partition(Xs,X,Left,Right),
quicksort(Left,Ls),
quicksort(Right,Rs),
append(Ls,[X|Rs],Ys).
quicksort([],[]).

partition([X|Xs],Y,[X|Ls],Rs) :-
X <= Y, partition(Xs,Y,Ls,Rs).
partition([X|Xs],Y,Ls,[X|Rs]) :-
X > Y, partition(Xs,Y,Ls,Rs).
partition([],Y,[],[]).

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

```

## python

```def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
if first<last:

splitpoint = partition(alist,first,last)

quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
pivotvalue = alist[first]

leftmark = first+1
rightmark = last

done = False
while not done:

while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp

temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp

return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)
```

## Scheme

```(define pHelper (lambda (all chk l m)
(cond ((null? all) (cons l (cons chk (cons m '()))))
(else
(let ((x (car all)))
(if (&lt;= x chk)
(pHelper (cdr all) chk (cons x l) m)
(pHelper (cdr all) chk l (cons x m))))))))

(define partition (lambda (l)
(pHelper (cdr l) (car l) '() '())))

(define quicksort (lambda (l)
(cond ((null? l) l)
(else
(let ((lx (partition l)))
```

## C

```#include <stdlib.h>
#include <stdio.h>

static void swap(void *x, void *y, size_t l) {
char *a = x, *b = y, c;
while(l--) {
c = *a;
*a++ = *b;
*b++ = c;
}
}

static void sort(char *array, size_t size, int (*cmp)(void*,void*), int begin, int end) {
if (end > begin) {
void *pivot = array + begin;
int l = begin + size;
int r = end;
while(l < r) {
if (cmp(array+l,pivot) <= 0) {
l += size;
} else if ( cmp(array+r, pivot) > 0 )  {
r -= size;
} else if ( l < r ) {
swap(array+l, array+r, size);
}
}
l -= size;
swap(array+begin, array+l, size);
sort(array, size, cmp, begin, l);
sort(array, size, cmp, r, end);
}
}

void qsort(void *array, size_t nitems, size_t size, int (*cmp)(void*,void*)) {
sort(array, size, cmp, 0, nitems*size);
}

typedef int type;

int type_cmp(void *a, void *b){ return (*(type*)a)-(*(type*)b); }

int main(void){ /* simple test case for type=int */
int num_list[]={5,4,3,2,1};
int len=sizeof(num_list)/sizeof(type);
char *sep="";
int i;
qsort(num_list,len,sizeof(type),type_cmp);
printf("sorted_num_list={");
for(i=0; i<len; i++){
printf("%s%d",sep,num_list[i]);
sep=", ";
}
printf("};\n");
return 0;
}
```

## ALGOL 68

```MODE DATA = INT;

PROC partition =(REF [] DATA array, PROC (REF DATA, REF DATA) BOOL cmp)INT: (
INT begin:=LWB array;
INT end:=UPB array;
WHILE begin < end DO
WHILE begin < end DO
IF cmp(array[begin], array[end]) THEN
DATA tmp=array[begin];
array[begin]:=array[end];
array[end]:=tmp;
GO TO break while decr end
FI;
end -:= 1
OD;
break while decr end: SKIP;
WHILE begin < end DO
IF cmp(array[begin], array[end]) THEN
DATA tmp=array[begin];
array[begin]:=array[end];
array[end]:=tmp;
GO TO break while incr begin
FI;
begin +:= 1
OD;
break while incr begin: SKIP
OD;
begin
);

PROC qsort=(REF [] DATA array, PROC (REF DATA, REF DATA) BOOL cmp)VOID: (
IF LWB array < UPB array THEN
INT i := partition(array, cmp);
PAR ( # remove PAR for single threaded sort #
qsort(array[:i-1], cmp),
qsort(array[i+1:], cmp)
)
FI
);

PROC cmp=(REF DATA a,b)BOOL: a>b;

main:(
[]DATA const l=(5,4,3,2,1);
[UPB const l]DATA l:=const l;
qsort(l,cmp);
printf((\$g(3)\$,l))
)
```

## AppleScript

```on QuickSort(aList, Le, Ri)
--> Sorts list of of simple types such as reals, integers, strings or even booleans
script Sal --> script object aList
property Array : aList
end script
set [i, j] to [Le, Ri]
set v to Sal's Array's item ((Le + Ri) div 2) --> pivot in middle (as C.A.R. Hoare's algorithm)
repeat while j > i
repeat while Sal's Array's item i < v
set i to i + 1
end repeat
repeat while Sal's Array's item j > v
set j to j - 1
end repeat
if not i > j then
tell (a reference to Sal's Array) to set [item i, item j] to [item j, item i] --> let's swap
set [i, j] to [i + 1, j - 1]
end if
end repeat
if Le < j then QuickSort(Sal's Array, Le, j)
if Ri > i then QuickSort(Sal's Array, i, Ri)
end QuickSort
```

## Assembly

``` qsort:  @ Takes three parameters:
@   a:     Pointer to base of array a to be sorted (arrives in r0)
@   left:  First of the range of indexes to sort (arrives in r1)
@   right: One past last of range of indexes to sort (arrives in r2)
@ This function destroys: r1, r2, r3, r5, r7
stmfd   sp!, {r4, r6, lr}     @ Save r4 and r6 for caller
mov     r6, r2                @ r6 <- right
qsort_tailcall_entry:
sub     r7, r6, r1            @ If right - left <= 1 (already sorted),
cmp     r7, #1
ldmlefd sp!, {r4, r6, pc}     @ Return, restoring r4 and r6
ldr     r7, [r0, r1, asl #2]  @ r7 <- a[left], gets pivot element
add     r2, r1, #1            @ l <- left + 1
mov     r4, r6                @ r <- right
partition_loop:
ldr     r3, [r0, r2, asl #2]  @ r3 <- a[l]
cmp     r3, r7                @ If a[l] <= pivot_element,
addle   r2, r2, #1            @ ... increment l, and
ble     partition_test        @ ... continue to next iteration.
sub     r4, r4, #1            @ Otherwise, decrement r,
ldr     r5, [r0, r4, asl #2]  @ ... and swap a[l] and a[r].
str     r5, [r0, r2, asl #2]
str     r3, [r0, r4, asl #2]
partition_test:
cmp     r2, r4                @ If l < r,
blt     partition_loop        @ ... continue iterating.
partition_finish:
sub     r2, r2, #1            @ Decrement l
ldr     r3, [r0, r2, asl #2]  @ Swap a[l] and pivot
str     r3, [r0, r1, asl #2]
str     r7, [r0, r2, asl #2]
bl      qsort                 @ Call self recursively on left part,
@  with args a (r0), left (r1), r (r2),
@  also preserves r4 and r6
mov     r1, r4
b       qsort_tailcall_entry  @ Tail-call self on right part,
@  with args a (r0), l (r1), right (r6)
```

## AutoIt v3

```  Func sort( ByRef \$array, \$left, \$right )
\$i = \$left
\$j = \$right
\$v = \$array[Round( ( \$left + \$right ) / 2 ,0)]
While ( \$j > \$i )
While (\$array[\$i] < \$v )
\$i = \$i + 1
WEnd
While ( \$array[\$j] > \$v )
\$j = \$j - 1
WEnd
If ( NOT (\$i > \$j) ) then
swap(\$array[\$i], \$array[\$j])
\$i = \$i + 1
\$j = \$j - 1
EndIf
WEnd
if ( \$left  < \$j ) then sort( \$array, \$left, \$j  )
if ( \$right > \$i ) then sort( \$array, \$i, \$right )
EndFunc
```