QuickSort

PHOTO

Mon Oct 31 2022 17:08:02 GMT+0000 (Coordinated Universal Time)

#include <stdio.h>

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

int partition(int array[], int low, int high) {
  
  int pivot = array[high];
  
  int i = (low - 1);

  for (int j = low; j < high; j++) {
    if (array[j] <= pivot) {
        
      i++;
      
      swap(&array[i], &array[j]);
    }
  }

  swap(&array[i + 1], &array[high]);
  
  return (i + 1);
}

void quickSort(int array[], int low, int high) {
  if (low < high) {
    
    int pi = partition(array, low, high);
    
    quickSort(array, low, pi - 1);
    
    quickSort(array, pi + 1, high);
  }
}

void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

int main() {
  int data[] = {8, 7, 2, 1, 0, 9, 6};
  
  int n = sizeof(data) / sizeof(data[0]);
  
  printf("Unsorted Array\n");
  printArray(data, n);
  
  quickSort(data, 0, n - 1);
  
  printf("Sorted array in ascending order: \n");
  printArray(data, n);
}

COPY

https://www.programiz.com/dsa/quick-sort

Save snippets that work from anywhere online with our extensions

Comments

More like this

#javascript #sort #typescript

Sort by boolean flags

const a = [
    {
        k: 1, me: false, prim: false
    }, {
        k: 2, me: false, prim: false
    }, {
        k: 3, me: false, prim: false
    }, {
        k: 4, me: false, prim: false
    }, {
        k: 5, me: true, prim: true
    }, {
        k: 6, me: false, prim: false
    }
]

a
    .sort((x, y) => (x.prim === y.prim) ? 0 : x.prim ? -1 : 1)
    .sort((x, y) => (x.me === y.me) ? 0 : x.me ? -1 : 1)

console.log(a)

#applescript #sort #files

Apple Script that sorts even pages to a new folder. Separates even from odd.

set srcFldr to (choose folder with prompt "Select the source folder:")
set destFldr to (choose folder with prompt "Select the destination folder:")
tell application "Finder"
	--set fileList to files of srcFldr -- sorted by name in HFS Plus' fashion (?)
	set fileList to sort (get files of srcFldr) by name -- sorted by name in Finder's fashion
	set fileCnt to count fileList
	set ff to {}
	repeat with i from 2 to fileCnt by 2
		set end of ff to item i of fileList
	end repeat
	move ff to destFldr -- you can move list at once
end tell

#modx #sortby #sort #id #resources #pdoresources

set sort by order by id MODX

 [[pdoResources?
                                        &parents=`0`
                                        &resources=`[[++company]], [[++new-products]], [[++used-products]], [[++koptika]], [[++services]], [[++brands]], [[++news]], [[++contact]]`
                                        &limit=`20`
                                        &depth=`10`
                                        &tpl=`footerLinksTPL`
                                        &sortby=`FIELD(modResource.id, [[++company]], [[++new-products]], [[++used-products]], [[++koptika]], [[++services]], [[++brands]], [[++news]], [[++contact]] )`
                                        &sortdir=`ASC`
                                        &showHidden=`1`
                                        &context=`[[!getContext]]`
                                    ]]

#javascript #array #sort

Sort array

const arr = [333,1,2,11,22,3,4]
console.log(arr.sort())

arr.sort((a,b)=>a-b)

console.log(arr)

#javascript #vanilla #sort #randomize #array

Custom sort : shuffle an array the quick way

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const shuffledArray = array.sort((a, b) => 0.5 - Math.random());

// using Array map and Math.random
const shuffledArr = array => array.map(a => ({ sort: Math.random(), value: a })).sort((a, b) => a.sort - b.sort).map(a => a.value);

#javascript #vanilla #sort #randomize #array

Fisher-Yates algorith : (Really) shuffle and array

const shuffleArray = array => {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    const temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}

#javascript #vanilla #sort #randomize #array

Durstenfeld shuffle algorithm : Optimized Fisher-Yates

function shuffle(array) {
  const curIdx = array.length;

  // While there remain elements to shuffle...
  while (0 !== cur_idx) {
    // Pick a remaining element...
    const randIdx = Math.floor(Math.random() * curIdx);
    curIdx -= 1;

    // And swap it with the current element.
    const originalIdx = array[curIdx];
    array[curIdx] = array[randIdx];
    array[randIdx] = originalIdx;
  }
  return array;
}

// Usage of shuffle
const arr = [1, 2, 3, 4, 5, 6];
arr = shuffle(arr);
console.log(arr);

// shorter
function shuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var originalIdx = array[i];
        array[i] = array[j];
        array[j] = originalIdx;
    }
}

//es6
function shuffle_array(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

#javascript #vanilla #sort #randomize #array

Shuffle a deck of cards

Example: Shuffle Deck of Cards

// program to shuffle the deck of cards

// declare card elements
const suits = ["Spades", "Diamonds", "Club", "Heart"];
const values = [
  "Ace",
  "2",
  "3",
  "4",
  "5",
  "6",
  "7",
  "8",
  "9",
  "10",
  "Jack",
  "Queen",
  "King",
];

// empty array to contain cards
let deck = [];

// create a deck of cards
for (let i = 0; i < suits.length; i++) {
    for (let x = 0; x < values.length; x++) {
        let card = { Value: values[x], Suit: suits[i] };
        deck.push(card);
    }
}

// shuffle the cards
for (let i = deck.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * i);
    let temp = deck[i];
    deck[i] = deck[j];
    deck[j] = temp;
}

console.log('The first five cards are:');

// display 5 results
for (let i = 0; i < 5; i++) {
    console.log(`${deck[i].Value} of ${deck[i].Suit}`)
}

//output
The first five cards are:
4 of Club
5 of Diamonds
Jack of Diamonds
2 of Club
4 of Spades

#aws #boto3 #sqs #fifo #sort

sqs-sort-records-into-fifo.py

# Standard
import json  # Not jason.
import random  # Fair dice roll.
import time  # As if we could.
import uuid  # Not GUID!

# Boto3/Moto
import boto3  # Client factory of typing doom.
import moto  # Love and sanity for the masses.

queue_name = "EventQueue"
fifo_queue_name = "EventQueueSorted.fifo"
event_types = ["solid", "liquid", "gas"]

# Mock me if you must!
sqs_mocker = moto.mock_sqs()
sqs_mocker.start()

# Set up client.
sqs_client = boto3.client("sqs", region_name="us-east-1")

# Create standard queue for incoming events so that we can batch it up.
sqs_create_queue_result = sqs_client.create_queue(
    QueueName=queue_name,
)

queue_url = sqs_create_queue_result["QueueUrl"]

# Create FIFO queue and allow for deduplication using event ID from
# event provider.
sqs_create_fifo_queue_result = sqs_client.create_queue(
    QueueName=fifo_queue_name,
    Attributes={
        "FifoQueue": "true",  # Stringy boolean!
        "DeduplicationScope": "messageGroup",  # No comment!
        "FifoThroughputLimit": "perMessageGroupId",  # I said no comment!
    },
)

fifo_queue_url = sqs_create_fifo_queue_result["QueueUrl"]

# Make some fake records using fake timestamps. Ignore this awful.
records = [
    {
        "timestamp": int(
            (time.time() * 1000) + random.randint(-10000, 10000),
        ),
        "event_type": random.choice(event_types),
        "event_id": str(uuid.uuid1()),
    }
    for timestamp in range(10)
]

# Do the hokey pokey
random.shuffle(records)

for record in records:
    print(record)

# {'timestamp': 1628905019640, 'event_type': 'liquid', 'event_id': '1d6d987b-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905015766, 'event_type': 'liquid', 'event_id': '1d6d987f-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905019341, 'event_type': 'gas', 'event_id': '1d6d9881-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905012019, 'event_type': 'solid', 'event_id': '1d6d9880-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905026503, 'event_type': 'liquid', 'event_id': '1d6d987c-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905024388, 'event_type': 'gas', 'event_id': '1d6d9882-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905017491, 'event_type': 'gas', 'event_id': '1d6d9883-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905013437, 'event_type': 'solid', 'event_id': '1d6d987e-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905012744, 'event_type': 'solid', 'event_id': '1d6d987d-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905010779, 'event_type': 'gas', 'event_id': '1d6d987a-fca0-11eb-9b68-cbb48e88eb48'}

# Pretend we are uberkitten.io and we are sending you 10 out of order
# records

entries = []

for record in records:
    sqs_send_message_result = sqs_client.send_message(
        QueueUrl=queue_url,
        MessageBody=json.dumps(record),
    )

# ... Pretend we pooled up a bunch of messages over 300 seconds.

# With a Lambda based subscription we can pool thousands of messages
# over a very long period up to a 1MB payload... here in moto land
# we don't have the luxury but we can imitate.

sqs_receiver_message_result = sqs_client.receive_message(
    QueueUrl=queue_url,
    MaxNumberOfMessages=10,
)

# ... Pretend we are a LAMBDA that is now receiving a ton of messages.

# Note: This would usually be a "Records" event and use different key
# casing just because.. yeh.

messages = sqs_receiver_message_result["Messages"]

# Convert body back to JSON for all the messages before we go on.
for message in messages:
    message["DecodedBody"] = json.loads(message["Body"])

# I'm still undecided about MSG
messages.sort(key=lambda message: message["DecodedBody"]["timestamp"])

entries = []

# Iterate through messages and create a new bulk of entries from the
# newly sorted list.
for message in messages:
    record = message["DecodedBody"]
    entries.append(
        {
            "Id": str(uuid.uuid1()),
            "MessageBody": message["Body"],
            "MessageGroupId": record["event_type"],
            "MessageDeduplicationId": record["event_id"],
        }
    )

# Enqueue FiFoables.
sqs_send_message_batch_results = sqs_client.send_message_batch(
    QueueUrl=fifo_queue_url,
    Entries=entries,
)

# ... Pretend we pooled up the maximum batch size for a FIFO queue..
# which is not hard to pretend at all.

sqs_receiver_message_result = sqs_client.receive_message(
    QueueUrl=fifo_queue_url,
    MaxNumberOfMessages=10,
)

# ... Pretend we are ANOTHER LAMBDA that will be processing the "sorted"
# messages.

messages = sqs_receiver_message_result["Messages"]

records_by_event_type = {}

for message in messages:
    message["DecodedBody"] = json.loads(message["Body"])
    record = message["DecodedBody"]

    records_by_event_type.setdefault(record["event_type"], [])
    records_by_event_type[record["event_type"]].append(record)


# And now demonstrate how out of control an article script can get.
for event_type, records in records_by_event_type.items():
    print(event_type)
    for record in records:
        print(record)

# gas
# {'timestamp': 1628905010779, 'event_type': 'gas', 'event_id': '1d6d987a-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905017491, 'event_type': 'gas', 'event_id': '1d6d9883-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905019341, 'event_type': 'gas', 'event_id': '1d6d9881-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905024388, 'event_type': 'gas', 'event_id': '1d6d9882-fca0-11eb-9b68-cbb48e88eb48'}
# solid
# {'timestamp': 1628905012019, 'event_type': 'solid', 'event_id': '1d6d9880-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905012744, 'event_type': 'solid', 'event_id': '1d6d987d-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905013437, 'event_type': 'solid', 'event_id': '1d6d987e-fca0-11eb-9b68-cbb48e88eb48'}
# liquid
# {'timestamp': 1628905015766, 'event_type': 'liquid', 'event_id': '1d6d987f-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905019640, 'event_type': 'liquid', 'event_id': '1d6d987b-fca0-11eb-9b68-cbb48e88eb48'}
# {'timestamp': 1628905026503, 'event_type': 'liquid', 'event_id': '1d6d987c-fca0-11eb-9b68-cbb48e88eb48'}

# How dare you mock me!
sqs_mocker.stop()

#php #sort #array

Multisort

array_multisort(array_map(function($element) {
  return $element['key'];
}, $result), SORT_ASC, $result);

#javascript #strings #regex #sort #anagram #loops #unsolved

Valid Anagram

// SOLUTION 1 - MY (DISCOVERED) SOLUTION (RUNTIME - 104MS, 44.9 MB)
var isAnagram = function(s, t) {
    
    // set function to split, sort, and rejoin characters in a string
    const sortString = (str) => {
        return str.split("").sort().join("");
    }
    
    // regex removes any non-alphabet characters in the string and makes it lowercase
    s = s.replace(/[^\w]/g, '').toLowerCase()
    t = t.replace(/[^\w]/g, '').toLowerCase()

    // final comparison
    return sortString(s) === sortString(t)
  
  // ATTEMPT 1
  //     let anagram = []
    
  // return false is lengths don't match
  //     if (s.length !== t.length) return false;
  //     else {
  //         for (let i = 0; i < s.length; i++) {
  //             let arrT = t.split("")
  //             let newArrT;
  //             if (arrT.includes(s.charAt(i))) {
  //                 let index = arrT.indexOf(s.charAt(i));
  //                 console.log("s char: ", s.charAt(i));
  //                 console.log("index: ", index);

  //                 anagram.push(s.charAt(i))

  //                 console.log("splice: ", arrT.splice(index, 1))
  //                 arrT.splice(index, 0)

  //                 newArrT = arrT
  //                 console.log("newArr: ", newArrT)
  //             };
  //         };
  //     }
  //     console.log(anagram)
  //     return anagram.join("") === s;
}

// SOLTUION 2 - (BEST RUNTIME - 60MS)
var isAnagram = function(s, t) {
    const key = w => Object.entries([...w].reduce((a, c) => {
        if (!(c in a)) a[c] = 0;
        a[c] += 1;
      
        return a;
    }, {})).sort(([c1], [c2]) => c1.localeCompare(c2)).flat().join('');
  
    return key(s) === key(t);
};

// SOLUTION 3 - (RUNTIME - 72MS)
var isAnagram = function(s, t) {
    if(s.length !== t.length) return false;
  
    let map = {};
  
    for(let item of s) {
        map[item] = map[item] + 1 || 1;
    }
    
    for(let item of t) {
        if(!map[item]) return false;
        else map[item]--;
    }
  
    return true;
};

#sort #python

Selection Sort in Python - Computer Notes

def sort(nums):
    for i in range(5):
         minpos = i
         for j in range(i,6):
            if nums[j] < nums[minpos]:
               minpos = j
               temp = nums[i]
               nums[i] = nums[minpos]
               nums[minpos] = temp
nums = [5,3,8,6,7,2]
sort(nums)
print(nums)

#ios #swift #xcode #sort #array #sortarray

Sort Array

self.postModel = self.postModel.sorted(by: { $0.time_stamp > $1.time_stamp

#javascript #sort #bubble

bubble sort

function bubbleSort(arr){
  let len = arr.length;
  let cost = 0;
  
  for(let i=0; i<len; i++){
    for(let j=0; j<len-1; j++){
      if(arr[j] > arr[j+1]){
        swap(arr, j, j+1);
      }
    }
  }
  return arr
}

let unsortedArr = [0, 5, 6, 8, 2, 1, 3, 7, 4, 10, 12, 11]

console.log(bubbleSort(unsortedArr))

#python #neetcode #sort

Group Anagrams into subsets: Python

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def Remove(lst): #to remove repeats at end 
            return ([list(i) for i in {*[tuple(sorted(i)) for i in lst]}]) 
    
    
        result = []
        for i in range(0, len(strs)): 
            anagram_subset = [strs[i]]
            sorted_string = sorted(strs[i]) 
            for d in range(0, len(strs)):
            #to avoid repeat 
            #maybe change to start, end pointers to avoid making duplicate in first place? 
                if d == i: 
                    continue 
                if sorted(strs[d]) == sorted_string: 
                    anagram_subset.append(strs[d])
            anagram_subset.sort()
            result.append(anagram_subset)
            anagram_subset = [] 
        return Remove(result) 

#Big O is n * n * n log N lol 

#more efficient solution 

	def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
          res = defaultdict(list) #map charCount to list of anagrams 

          for s in strs: 
            count = [0] * 26 # a ... z 

            for c in s: 
              count[ord(c) - ord("a")] += 1 #mapping to ASCII and then adding 1 so that a = 1, b = 2, etc. 

              res[tupule(count)].append(s) 

          return res.values()

        #big O(m * n * 26) which is just (m * n)

QuickSort

Save snippets that work from anywhere online with our extensions

Comments

More like this

Browse more snippets >>

Embed code snippet