DZone Snippets: sort code

Merge-sort

scvalex (Alexandru Scvortov) — Fri, 28 Sep 2007 06:40:13 GMT

Implements the classic Merge-sort algorithm.

Time: theta(lg(n))
Space: theta(n)



#include 

#include 

#include 



void printv(char* in, int *v, int n) {

	printf("%s", in);

	int i = 0;

	for (; i < n; ++i)

		printf("%d ", v[i]);

	printf("\n");

}



void merge(int *v, int p, int q, int r) {

	int i = p;

	int j = q + 1;

	

	int *tmp = (int*)malloc((r - p + 1) * sizeof(int));

	int k = 0;

	

	while ((i <= q) && (j <= r)) {

		if (v[i] < v[j])

			tmp[k++] = v[i++];

		else

			tmp[k++] = v[j++];

	}

	

	while (i <= q)

		tmp[k++] = v[i++];

	

	while (j <= r)

		tmp[k++] = v[j++];

	

	memcpy(v + p, tmp, (r - p + 1) * sizeof(int));

	free(tmp);

}



void mergeS(int *v, int p, int r) {

	if (p < r) {

		int q = (p + r) / 2;

		mergeS(v, p, q);

		mergeS(v, q + 1, r);

		merge(v, p, q, r);

	}

}



int main(int argc, char *argv[]) {

	int n = 10;

	int v[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1};

	

	printv("V: ", v, n);

	mergeS(v, 0, n - 1);

	printv("V: ", v, n);

	

	return 0;

}

Sort generic list

mstampar (Miroslav Stampar) — Thu, 07 Jun 2007 19:06:38 GMT



public class Item

{

 public Item(string term, int freq)

 {

  _term = term;

  _freq = freq;

 }



 private string _term;

 public string Term

 {

  get { return _term; }

  set { _term = value; }

 }



  private int _freq;

  public int Freq

  {

   get { return _freq; }

   set { _freq = value; }

  }

 }



 public class ItemComparer:IComparer

 {

  #region IComparer Members



  public int Compare(Item x, Item y)

  {

   return y.Freq - x.Freq; //descending sort

   //return x.Freq - y.Freq; //ascending sort

  }



  #endregion

 }



static void Main()

{

 List items = new List();

 ....

 items.Sort(new ItemComparer());

}

C - Insertion sort

scvalex (Alexandru Scvortov) — Wed, 09 May 2007 08:32:32 GMT

Classic implementation of the Insertion Sort algorithm.



void isort_c(unsigned *a, int n) {

  int k;

  for (k = 1; k < n; ++k) {

    int key = a[k];

    int i = k - 1;

    while ((i >= 0) && (key < a[i])) {

      a[i + 1] = a[i];

      --i;

    }

    a[i + 1] = key;

  }

}

Sort by frequency and order in a list

angshuman (Angshuman) — Sun, 18 Mar 2007 09:10:26 GMT

// You have an array. For eg [23,12,45,23,9,23,45]. Now you have to print the elements in the order of decreasing frequency, and the same no of times as it is coming in the imput aray. The output for this eg would be 23[3]45[2]12[1]9[1].If frequency of two elements is equal, they should come in the same order as they are coming in the input array.



struct Node

{

    int element;

    int frequency;

    int order;

    struct Node *next;

    struct Node *prev;

};



class FreqList {



 public:

    FreqList();

    virtual ~FreqList();

    virtual void addElement(int newEl);

    virtual void Print();

    virtual void createSorted();

    virtual void printSorted();



 private:

    void addAtEnd(int val, int freq, int order);

    Node* findElement(int val); 

    Node* partition(Node *head, Node *tail, int pivot);

    bool  deleteAfter(Node *p, int &val, int &freq, int &order);

    void insertSorted(int val, int freq, int order);

    void addAfter(Node *p, int val, int freq, int order);

    bool deleteFirst(int &val,int &freq, int &order);

    int orderOfElement;

    int numElements;



    Node *dummy;

    Node *dummySorted;

    Node *tail;



};





#include 

#include "FreqList.h"

#include 

#include 



FreqList::FreqList() {

    dummy = new Node;

    dummy->next = NULL;

    tail = dummy;

    dummySorted = new Node;

    dummySorted->next = NULL;

    numElements = 0;

    orderOfElement = 0;

}



FreqList::~FreqList() {

    //lot of cleanup to be done

}



void FreqList::addAtEnd(int val, int freq, int order) {

    Node *temp = new Node;

    temp->element = val;

    temp->frequency = freq;

    temp->order = order;

    temp->next = NULL;



    if(tail != NULL) {

	tail->next = temp;

	tail = temp;

    }

    else

	printf("Oooops!\n");

}



/* This will return a pointer whose next is the desired node */

Node * FreqList::findElement(int val) {

    Node *temp = dummy;

    while(temp->next != NULL) {

	if(temp->next->element == val)

	    return temp;

	else

	    temp=temp->next;

    }

    return NULL;

}



void FreqList::addElement(int newEl) {

    Node *temp;

    ++numElements;

    temp = findElement(newEl);

    if(temp == NULL) {

	//element not found. New element to be added

	addAtEnd(newEl, 1, ++orderOfElement);

	return;

    }

    else {

	if(temp->next != NULL) {

	    temp->next->frequency += 1;

	}

	else

	    printf("Hmmph!\n");

	return;

    }

}



void FreqList::insertSorted(int val, int freq, int order) {

    Node *p = dummySorted;

    while(p->next != NULL) {

	if(freq < p->next->frequency ) {

	    p = p->next;

	}

	else if(freq == p->next->frequency) {

	    if(order > p->next->order) {

		p = p->next;

	    }

	    else {

		break;

	    }

	}

	else {

	    break;

	}

    }

    addAfter(p, val, freq, order);

}



void FreqList::createSorted() {

    int val, freq, order;

    Node *temp = dummy;

    while(temp->next != NULL) {

	val = temp->next->element;

	freq = temp->next->frequency;

	order = temp->next->order;

	insertSorted(val, freq, order);

	temp = temp->next;

    }

}



void FreqList::printSorted() {

    Node *temp = dummySorted;

    while(temp->next != NULL) {

	printf("%d[%d]{%d} ", temp->next->element, temp->next->frequency, \

	       temp->next->order);

	temp = temp->next;	

    }

    printf("\n");

}





void FreqList::addAfter(Node *p, int val, int freq, int order) {

    Node *temp = new Node;

    temp->element = val;

    temp->frequency = freq;

    temp->order = order;



    temp->next = p->next;

    p->next = temp;

}



void FreqList::Print() {

    Node *temp = dummy;

    while(temp->next != NULL) {

	printf("%d[%d]{%d} ", temp->next->element, temp->next->frequency, \

	       temp->next->order);

	temp = temp->next;

    }

    printf("\n");

} 



int main()

{

    int arr[] = {12,12,23,45,23,9,23,45};

    int num;

    FreqList *freqList = new FreqList();



    srand((unsigned)time(0));





    for(int i=0; i<8000; i++)

    {   

        num = (rand()%10)+1;

        //printf("Step: %d El: %d ", i, arr[i] );

        freqList->addElement(num);

    }   

    freqList->Print();

    freqList->createSorted();

    freqList->printSorted();

    return 0;

}

PHP: Sorting an associative array

alexwilliams (Alex Williams) — Tue, 20 Feb 2007 15:02:58 GMT

This basically sorts an associative array... somethin' like that.



$people = new Array();



$people[0]['id'] = 1;

$people[0]['name'] = "Dave";

$people[1]['id'] = 2;

$people[1]['name'] = "Alex";

$people[2]['id'] = 3;

$people[2]['name'] = "Chris";



function cmp($a, $b)

{

   return strcmp($a['name'], $b['name']);

}

usort($people, "cmp");

Sort file by length of lines

AlpT (AlpT) — Sun, 14 Jan 2007 03:41:12 GMT

Sort file by length of lines



cat $@ | awk '{ print length, $0 }' | sort -n | awk '{$1=""; print $0}'

Perl: Sorted union of two arrays

nilesh (Nilesh) — Wed, 29 Nov 2006 12:45:19 GMT

Create a union of two arrays and sort the array.



my @union = array_union_sort(\@first, \@second);



sub array_union_sort {

    my $aa = shift;

    my $bb = shift;

    my %union;

    my $e;

    foreach $e (@$aa) { $union{$e} = 1; }

    foreach $e (@$bb) { $union{$e} = 1; }

    my @union = keys %union;

    @union = sort { $a <=> $b } @union;

    return @union;

}

Sort multiple dimensional arrays by column without the need to extract the column data first.

RQuadling (Richard Quadling) — Mon, 06 Nov 2006 18:36:27 GMT

A mechanism to sort multidimensional data by columns without the need to extract the column data first.

The syntax is the same as array_multisort().

You also have 3 additional parameters you can use:

AMC_SORT_STRING_CASELESS to sort the strings case insensitively.
AMC_LOSE_ASSOCIATION (the default behaviour) to lose the associations for the array.
AMC_KEEP_ASSOCIATION to keep the associations for the array.

If your array does not have associated indexes, then you can use column numbers. But watch out. If you also use PHP's constants like SORT_ASC, SORT_DESC, SORT_REGULAR, SORT_NUMERIC or SORT_STRING, then these can be mixed up with column numbers.
So, to remove this problem, I've created copies of these constants:
AMC_SORT_ASC
AMC_SORT_DESC
AMC_SORT_REGULAR
AMC_SORT_NUMERIC
AMC_SORT_STRING

Other than that, these function work together JUST like array_multisort but sorts using column(s) without the need to first extract the columns into individual arrays.



/*

(C) UK 2006 Richard Quadling



This work is licensed under the Creative Commons Attribution 2.5 License.

To view a copy of this license, visit http://creativecommons.org/licenses/by/2.5/ or send a letter to

    Creative Commons,

    543 Howard Street,

    5th Floor,

    San Francisco,

    California,

    94105, USA.



Version History



2006/09/20

Removed reliance on PHP's constants as using column numbers conflicted with these constants.

Use AMC_SORT_xxx rather than SORT_xxx.



2006/08/23

Added CC license

Added notice and error for parameters



2006/08/22

Fixed local defines to be well out of the way of the ones used by PHP.



2006/08/07

Created this code based upon work done by KES (http://www.php.net/manual/en/function.array-multisort.php#68452)

*/



// AMC defines for keeping association.

define ('AMC_LOSE_ASSOCIATION', 'AMC10001');

define ('AMC_KEEP_ASSOCIATION', 'AMC10002');



// AMC defines for the global array.

define ('AMC_SORT_ORDER', 'AMC10003');

define ('AMC_SORT_TYPE', 'AMC10004');



// AMC defines for the sort order.

define ('AMC_SORT_ASC', 'AMC10005');

define ('AMC_SORT_DESC', 'AMC10006');



// AMC defines for sorting type.

define ('AMC_SORT_REGULAR', 'AMC10007');

define ('AMC_SORT_NUMERIC', 'AMC10008');

define ('AMC_SORT_STRING', 'AMC10009');

define ('AMC_SORT_STRING_CASELESS', 'AMC10010');



/**

  * bool array_multisort_column ( array ar1 [, mixed arg [, mixed ... [, array ...]]] )

  **/

function array_multisort_column(array &$a_data, $m_mixed1)

    {

    // Get the parameters and the number of parameters.

    $a_Args = func_get_args();

    $i_Args = func_num_args();



    // Define a global empty array for the comparison function.

    $GLOBALS['a_AMC_ordering'] = array();



    // Get the list of columns.

    $a_Columns = array_keys(reset($a_data));



    // Assume association is NOT kept

    $b_KeepAssociation = False;



    // Process the parameter list, extracting columns and any applicable settings.

    for($i_Arg = 1 ; $i_Arg < $i_Args ; )

        {

        // Initially we only want to look at columns.

        if (in_array($a_Args[$i_Arg], $a_Columns))

            {

            // Track the column.

            $s_Column = $a_Args[$i_Arg];



            // Add the column with default settings to the global array.

            $GLOBALS['a_AMC_ordering'][$a_Args[$i_Arg]] = array

                (

                AMC_SORT_ORDER => AMC_SORT_ASC,

                AMC_SORT_TYPE => AMC_SORT_REGULAR,

                );



            // While there are more parameters to process is the next one a controller rather than a column.

            while

                (



                // There IS a next parameter.

                isset($a_Args[$i_Arg + 1]) && 



                // It is a controller.

                in_array

                    (

                    $a_Args[$i_Arg + 1], 

                    array

                        (

                        AMC_KEEP_ASSOCIATION,

                        AMC_LOSE_ASSOCIATION,

                        AMC_SORT_STRING_CASELESS,

                        AMC_SORT_ASC,

                        AMC_SORT_DESC,

                        AMC_SORT_NUMERIC,

                        AMC_SORT_REGULAR,

                        AMC_SORT_STRING,

                        ), 

                    True

                    )



                )

                {

                // Deal with column sorting order.

                if (

                    in_array

                        (

                        $a_Args[$i_Arg + 1], 

                        array

                            (

                            AMC_SORT_ASC, 

                            AMC_SORT_DESC

                            ), 

                        True

                        )

                    )

                    {

                    $GLOBALS['a_AMC_ordering'][$s_Column][AMC_SORT_ORDER] = $a_Args[$i_Arg + 1];

                    }

                // Deal with column sorting type.

                elseif (

                    in_array

                        (

                        $a_Args[$i_Arg + 1], 

                        array

                            (

                            AMC_SORT_REGULAR, 

                            AMC_SORT_NUMERIC, 

                            AMC_SORT_STRING, 

                            AMC_SORT_STRING_CASELESS

                            ), 

                        True

                        )

                    )

                    {

                    $GLOBALS['a_AMC_ordering'][$s_Column][AMC_SORT_TYPE] = $a_Args[$i_Arg + 1];

                    }

                // Deal with array association.

                else

                    {

                    $b_KeepAssociation = (AMC_KEEP_ASSOCIATION == $a_Args[$i_Arg + 1]);

                    }

                // Take the next argument out of the picture.

                ++$i_Arg;

                }

            }

        // Allow array association to be defined.

        elseif (

            in_array

                (

                $a_Args[$i_Arg], 

                array

                    (

                    AMC_KEEP_ASSOCIATION, 

                    AMC_LOSE_ASSOCIATION

                    ), 

                True

                )

            )

            {

            $b_KeepAssociation = (AMC_KEEP_ASSOCIATION == $a_Args[$i_Arg]);

            }

        // Ignore sort options as they are not in the right place to be understood.

        elseif (

            in_array

                (

                $a_Args[$i_Arg], 

                array

                    (

                    AMC_SORT_REGULAR, 

                    AMC_SORT_NUMERIC, 

                    AMC_SORT_STRING, 

                    AMC_SORT_STRING_CASELESS

                    ), 

                True

                )

            )

            {

            trigger_error("Parameter $i_Arg of '{$a_Args[$i_Arg]}' is not applicable and has been ignored.", E_USER_NOTICE);

            }

        // Whatever is left is an error.

        else

            {

            trigger_error("Requested column of '{$a_Args[$i_Arg]}' is not present in the supplied array.", E_USER_ERROR);

            }

        // Get the next argument.

        ++$i_Arg;

        }



    // Determine which usort mechanism (with or without associations).

    $s_Sorter = ($b_KeepAssociation ? 'uasort' : 'usort');



    // Sort the data and get the result.

    $b_Result = $s_Sorter($a_data, 'array_multisort_column_cmp');



    // Remove the temporary global array.

    unset($GLOBALS['a_AMC_ordering']);



    // Return the results

    return $b_Result;

    }



/**

  * int array_multisort_column_cmp(array a_left, array a_right)

  **/

function array_multisort_column_cmp(array &$a_left, array &$a_right)

    {

    // Assume that the entries are the same.

    $i_Result = 0;



    // Process each column defined in the global array.

    foreach($GLOBALS['a_AMC_ordering'] as $s_Column => $a_ColumnData)

        {

        // Handle the different sort types.

        switch ($a_ColumnData[AMC_SORT_TYPE])

            {

            // Numeric.

            case AMC_SORT_NUMERIC :

                $i_ColumnCompareResult = 

                    ((intval($a_left[$s_Column]) == intval($a_right[$s_Column])) 

                    ? 

                        0 

                    : 

                        ((intval($a_left[$s_Column]) < intval($a_right[$s_Column])) 

                        ? 

                            -1 

                        : 

                            1

                        )

                    );

                break;

            // Case sensitive strings.

            case AMC_SORT_STRING :

                $i_ColumnCompareResult = strcmp((string)$a_left[$s_Column], (string)$a_right[$s_Column]);

                break;

            // Case insensitive strings.

            case AMC_SORT_STRING_CASELESS :

                $i_ColumnCompareResult = strcasecmp((string)$a_left[$s_Column], (string)$a_right[$s_Column]);

                break;

            // Regular sorting.

            case AMC_SORT_REGULAR :

            default :

                $i_ColumnCompareResult = 

                    (($a_left[$s_Column] == $a_right[$s_Column]) 

                    ? 

                        0 

                    : 

                        (($a_left[$s_Column] < $a_right[$s_Column]) 

                        ? 

                            -1 

                        : 

                            1

                        )

                    );

                break;

            }

        // Is the column in the two arrays the same?

        if (0 == $i_ColumnCompareResult)

            {

            // Continue with the next column.

            continue;

            }

        // Are we sorting descending?

        $i_Result = $i_ColumnCompareResult * (($a_ColumnData[AMC_SORT_ORDER] == AMC_SORT_DESC) ? -1 : 1);



        // As there is a difference, we do not need to continue with the remaining columns.

        break;

        }



    // Return the result.

    return $i_Result;

    }

?>

sort-by-length - sort a series by element length

gregg.irwin (Gregg Irwin) — Mon, 02 Oct 2006 23:21:03 GMT



    sort-by-length: func [series] [sort/compare series :cmp-length]

cmp-length - compare the length of two series and return -1, 0, or 1, to support stable sorts by length

gregg.irwin (Gregg Irwin) — Mon, 02 Oct 2006 23:19:39 GMT



    ; Support func for stable sort comparator

    cmp-length: func [a [series!] b [series!] /local len-a len-b] [

        len-a: length? a

        len-b: length? b

        case [

            len-a < len-b [-1]

            len-a > len-b [1]

            len-a = len-b [0]

        ]

    ]