Quick Sort Implementation in C

Quicksort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959, published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.Sorting_quicksort_anim

Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.
Mathematical analysis of quicksort shows that, on average, the algorithm takes O(nlogn) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare. [Wikipedia]

Here is implementation in C.

#include <stdio.h>

void quicksort(int a[], int left, int right);
int  partition(int a[], int left, int right);

int main(int argc, const char * argv[])
{
    int numbers[] = {5, 1, 0, 4, 2, 3};
    int size = sizeof(numbers)/sizeof(numbers[0]);
    int i;
    
    printf("unsorted:");
    for (i=0;i<size;i++) printf("%d ", numbers[i]);
    printf("\n");
    
    quicksort(numbers, 0, size - 1);
    
    printf("  sorted:");
    for (i=0;i<size;i++) printf("%d ", numbers[i]);
    printf("\n");
    
    return 0;
}


void quicksort(int list[], int left, int right)
{
    int pivotIndex;
    if ( left &lt; right)
    {
        pivotIndex = partition(list, left, right);
        quicksort(list, left, pivotIndex - 1);
        quicksort(list, pivotIndex + 1, right);
    }
}

int partition(int list[], int left, int right)
{
    int low, high, t, pivot;
    pivot = list[left];
    low = left;
    high = right + 1;
    while (low < high)
    {
        do ++low; while (list[low] <= pivot && low < right); 
        do --high; while (list[high] > pivot);
        
        if (low < high ) {
            t = list[low]; list[low] = list[high]; list[high] = t;
        }
    }
    
    t = list[left]; list[left] = list[high]; list[high] = t;
    
    return high;
}

Sort a Scrambled Itinerary

This algorithm problem is from Google Code Jam. Here is the description of the problem.

Once upon a day, Mary bought a one-way ticket from somewhere to somewhere with some flight transfers.
For example: SFO->DFW DFW->JFK JFK->MIA MIA->ORD.
Obviously, transfer flights at a city twice or more doesn’t make any sense. So Mary will not do that.
Unfortunately, after she received the tickets, she messed up the tickets and she forgot the order of the ticket.
Help Mary rearrange the tickets to make the tickets in correct order.

Input
The first line contains the number of test cases T, after which T cases follow.
For each case, it starts with an integer N. There are N flight tickets follow.
Each of the next 2 lines contains the source and destination of a flight ticket.

Output
For each test case, output one line containing “Case #x: itinerary”, where x is the test case number (starting from 1) and itinerary is sorted list of flight tickets which represents the actual itinerary. Each flight segment in the itinerary should be outputted as pair of source-destination airport codes.

Limits

1 ≤ T ≤ 100.
For each case, the input tickets are messed up from an entire itinerary bought by Mary. In other words, it’s ensured can be recovered to a valid itinerary.
1 ≤ N ≤ 10^4.
(The segment for second case in sample can be seen as below) MIA-ORD, DFW-JFK, SFO-DFW, JFK-MIA

Sample : 

Input
2
1
SFO
DFW
4
MIA
ORD
DFW
JFK
SFO
DFW
JFK
MIA

Output
Case #1: SFO-DFW
Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD

Here is my solution code. I have stored all destinations (as integer) in array element of departures (as integer).
First, we find a starting airport, which is marked as iDest = 0.  And recursively print departure-destination pairs.

/*
 ============================================================================
 Name        : CodeJam-ScrambledItinerary.c
 Author      : Elmurod Talipov
 Description : Problem C. Sort a scrambled itinerary
 ============================================================================
 */

#define  MAXCOM 	  (26*26*26 + 26*26 + 26+1)
#include <stdio.h>

int  N, iPair[MAXCOM];
char iDst[MAXCOM];
char iName[MAXCOM][4];

int main(void)
{
	int T, tc;
	int i, s, d;
	char STR[10];

	//freopen("input.txt", "r", stdin);
	scanf("%d", &T);
	for (tc = 1; tc <= T; tc++)
	{
		for (i = 0; i < MAXCOM; i++)
		{
			iPair[i] = -1;
			iDst[i] = 0;
		}

		scanf("%d", &N);
		for (i = 0; i < N; i++)
		{
			scanf("%s", STR);
			s = (STR[0] - 'A')*26*26 +  (STR[1] - 'A')*26 + (STR[2] - 'A');
			iName[s][0] = STR[0];
			iName[s][1] = STR[1];
			iName[s][2] = STR[2];
			iName[s][3] = '\0';

			scanf("%s", STR);
			d = (STR[0] - 'A')*26*26 +  (STR[1] - 'A')*26 + (STR[2] - 'A');
			iName[d][0] = STR[0];
			iName[d][1] = STR[1];
			iName[d][2] = STR[2];
			iName[d][3] = '\0';

			iPair[s] = d;
			iDst[d] = 1;
		}

		for (i=0;i<MAXCOM;i++)
			if ((iPair[i] != -1) && (iDst[i] == 0))
			{
				s = i;
				break;
			}

		printf ("Case #%d:", tc);
		while (N > 0)
		{
			d = iPair[s];
			printf(" %s-%s", iName[s], iName[d]);
			s = d;
			N--;
		}
		printf("\n");
	}

	return 0;
}

Web server in one line of shell code

If you want to quickly save a file through http but you don’t want to install a web server, you can just use netcat.

You can run:

 while true; do { echo -e 'HTTP/1.1 200 OK\r\n'; cat index.html; } | nc -l 8080; done 

index.html can be any file you want to serve it.

You can access it after that as: http://<YOUR HOST>:8080/

Linux Kernel boot sequence

Execution in Assembly

Entry point for Kernel uncompressed – arch/arm/kernel/head.S
  1. Read processor ID in coprocessor and obtain proc_info_list pointer
  2. Lookup machine type based on mach-id passed by bootloader (R1), get the mach_desc pointer and save mach-id
  3. Determine vailidity of ATAGS pointer (R2) and save
  4. Setup minimal pagetable to get Kernel running on virtual address, also setup one-to-one mapping for the page that turns on MMU
  5. Initialize TLB, caches, setup MMU to be turned on
  6. Turn on MMU
  7. Branch to start_kernel

Execution in C

C entry point – start_kernel() init/main.c
  1. Disable IRQ local_irq_disable()
  2. Print Linux banner
  3. Arch specific setup setup_arch() (arch/arm/kernel/setup.c)
    1. Using mach-id, get pointer to machine_desc (defined in board file)
    2. Using ATAG physical pointer, obtain virtual address
    3. Invoke machine specific fixup
    4. Save & parse ATAGS parse_atags() (arch/arm/kernel/setup.c)
    5. Parse early params parse_early_params
    6. arm_memblock_init (arch/arm/mm/init.c)
      1. Invoke machine specific reserve
    7. Setup pagetables paging_init (arch/arm/mm/mmu.c)
      1. prepare_pagetable
      2. Map memory banks
      3. Map machine vectors devicemaps_init
      4. Invoke machine specific map_io
      5. Allocate zero page
      6. bootmem_init (arch/arm/mm/init.c)
    8. Install vectors early_trap_init (arch/arm/kernel/traps.c)
    9. Invoke machine specific init_early
  4. Build memory zone list build_all_zonelists() (mm/pagealloc.c)
  5. Print Kernel command line
  6. Parse early params
  7. Parse commandline args parse_args (kernel/params.c)
  8. pid hashtable initialization
  9. Setup Kernel memory allocators mm_init
    1. Mark free areas in memory & print memory details
    2. Initialize page cache
    3. Initialize vmalloc
  10. Initialize scheduler sched_init
  11. Disable preemption
  12. Initialize RCU, radix tree
  13. early_irq_init (kernel/irq/irqdesc.c)
  14. Invoke machine specific init_irq
  15. Initialize software timers, soft irq init_timers (kernel/timer.c), softirq_init (kernel/softirq.c)
  16. Initialize clocksource & common timekeeping values timekeeping_init (kernel/time/timekeeping.c)
  17. time_init (arch/arm/kernel/time.c)
    1. Get machine specific timer
    2. Invoke machine specific timer->init
    3. sched_clock post init
  18. Enable IRQ
  19. Initialize console device (if console_initcall) console_init (drivers/tty/tty_io.c)
  20. kmem_leak_init (mm/kmemleak.c)
  21. Allocate per_cpu pagesets setup_per_cpu_pageset (mm/pagealloc.c)
  22. Initialize NUMA policy numa_policy_init (mm/mempolicy.c)
  23. calibrate_delay (init/calibrate.c)
  24. Initialize pid map pidmap_init (kernel/pid.c)
  25. Initialize anonymous vma anon_vma_init (mm/rmap.c)
  26. Initialize init process structure fork_init (kernel/fork.c)
  27. Initialize security framework security_init (security/security.c)
  28. Initialize kdb kdb_init (kernel/debug/kdb/kdb_main.c)
  29. Initialize caches for VFS vfs_caches_init (fs/dcache.c)
  30. Initialize proc FS proc_root_init (fs/proc/root.c)
  31. Initialize ftrace ftrace_init (kernel/trace/ftrace.c)
  32. rest_init (in non-init section)
    1. Spawn init process
    2. Spawn kthreadd
    3. Wait till kthreadd is setup
    4. Enable preemption
    5. schedule schedule (kernel/sched.c)
    6. Disable preemption
    7. cpu_idle (arch/arm/kernel/process.c)

process – 1 (init process) kernel_init (init/main.c)

  1. Wait till kthreadd is setup
  2. do_basic_setup
    1. Create usermode helper wq usermodehelper_init (kernel/kmod.c)
    2. Initialize tmpfs init_tmpfs (mm/shmem.c)
    3. Initialize driver model driver_init (drivers/base/init)
    4. Call initcalls as per the order (machine specific init_machine would get called due to this) do_initcalls
  3. prepare_namespace (init/do_mounts.c)
    1. Load initrd initrd_load (init/do_mounts_initrd.c)
      1. Identify decompressor method identify_ramdisk_image (init/do_mounts_initrd.c)
      2. Create memory for uncompressed FS
      3. Decompress FS and copy crd_load (init/do_mounts_rd)
    2. Mount root FS mount_root (init/do_mounts.c)
  4. init_post (in non-init section)
    1. Free memory in init section free_initmem (arch/arm/mm/init.c)
    2. Replace process – 1 (a kernel thread) with userspace init process, by exec in kernel run_init_process

Credit : Suresh Thiagarajan