מיונים – אוסף סוגי מיונים

bennyכלליLeave a Comment

מיון בועות

#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
la $a0 ,str1        # load string adress to $a0
syscall             # pirnt "ENTER VALUE"
li $v0,5           
syscall             # cin >> int
add $t0,$0,$v0
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
la $a0 ,str1        # load string adress to $a0
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 '*'
add_: 
add $t0,$t0,$v0
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:
add $a0 ,$0,$t0         
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([Head|List]) :-
        write(Head, " "),
        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();
 
            Console.ReadLine();
        }
 
        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)))
                            (append (quicksort (car lx)) (cons (cadr lx) (quicksort (caddr lx)))))))))

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

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *