SORTING TECHNIQUES

SORTING ALGORITHMS

Sorting is the process that organizes the collection of data either in ascending or descending order.

there will be two sorting process.They are

   1.Internal sorting
   2.External sorting

Internal sorting:
  Internal sorting is the process in which sorting is to be done within the computer's memory.
  External sorting needs externa memory such as HardDisks for sorting process.

There are many sorting algorithms:

  1.Insertion sort
  2.Selection sort
  3.Bubble sort
  4.Merge sort
  5.Quick sort

Selection sort:
In the list is divided into two sublists, sorted and unsorted.

We find the smallest element from the unsorted sublist and swap it with the element at the beginning of the unsorted data.

Each time we move one element from the unsorted sublist to the sorted sublist, we say that we have completed a sort pass.

A list of n elements requires n-1 passes to completely rearrange the data.

A list of n elements require n-1 passes to arranging the data. 

Bubble sort:

In the list is divided into two sublists, sorted and unsorted.

The smallest element is bubbled from the unsorted list and move the element at the beginning of the sorted sublist.

Each time we move one element from the unsorted list to the sorted sublist, we say that we have completed a sort pass.

A list of n elements requires n-1 passes to completely rearrange the data.

A list of n elements require n-1 passes to arranging the data. 

 

comparision:

Selection sort:
Worst scenario: O(n2);
Average scenario: O(n2);
Best scenario: O(n2);

Bubble sort:
Worst scenario: O(n2);
Average scenario: O(n2);
Best scenario: O(n2);

Modified Bubble sort:

Worst scenario: O(n2);
Average scenario: O(n);
Best scenario: O(n);

The selection sort and bubble sort performance wise both are same.But the method of sorting is different with each other.

The difference between the bubble sort and modified bubble sort is modified bubble sor tis decreasing the number of steps used for sorted process.

Insertion sort.

In this method, sorting is done by inserting elements into an existing sorted list.
Initially, the sorted list has only one element.
Other elements are gradually added into the list in the proper position.

Merge Sort:

Merge sort is one of the Sorting Technique which is based on divide and conquer mechanism.

In this method,initially then given  elements are partially divided,and again they divided using recursive method.

After partioning of elements the first half and second half of the elements sorted seperatedly and then they have merged together.

Application of Merge Sort:

1.It can handle large amount of data and process it quickly.

2.It is also used to merge the two sorted lists.

Quick sort:

Quick sort is a most efficient algorithm as compared to selection or bubble sort.

It works by first of all by partitioning the array around a pivot value and then dealing with the 2 smaller partitions separately.

 

Partitioning is the most complex part of quick sort.

The simplest thing is to use the first value in the array,  as the pivot.

After the partitioning, all values to the left of the pivot are <= pivot

and all values to the right are > pivot.This gives better performance.

The approach of Quick sort is called Depth fast approach.

Best case running time of quick sot is O(n log2 n).

Worst case is O(n2).

Booting:

    Booting is a process or set of operations that loads and hence starts the operating system, starting from the point when user switches on the power button.


Boot Loader:

    A boot loader is a type of program that loads and starts the boot time tasks and processes of an operating system or the computer system.

It enables loading the operating system within the computer memory when a computer is started or booted up.

A boot loader is also known as a boot manager.

Booting Sequence:
       
Boot sequence is the order in which a computer searches for nonvolatile data storage devices containing program code to load the operating system .

Typically, a Macintosh structure uses ROM and Windows uses BIOS to start the boot sequence.

Once the instructions are found, the CPU takes control and loads the OS into system memory.

The devices that are usually listed as boot order options in the BIOS settings are hard disks, floppy drives, optical drives, flash drives, etc.

The user is able to change the boot sequence via the CMOS setup. Boot sequence is also called as boot order or BIOS boot order.

The Booting Sequence is Follows:

   
     Turn on the Power button.
        
    CPU pins are reset and registers are set to specific value.
        
     CPU jump to address of BIOS (0xFFFF0).
        
     BIOS run POST (Power-On Self Test) and other necessary checks.
        
     BIOS jumps to MBR(Master Boot Record).
        
     Primary Bootloader runs from MBR and jumps to Secondary Bootloader.
        
     Secondary Bootloaders loads Operating System.

These are the tasks that are carried during booting process.

BOOTSTRAPPING

BOOT STRAP:

    Bootstrap is the process of loading a set of instructions when a computer is first turned on or booted.

During the start-up process, diagnostic tests are performed, such as the power-on self-test (POST), that set or check configurations for devices and implement routine testing for the connection of peripherals, hardware and external memory devices.

The boot loader or bootstrap program is then loaded to initialize the OS.

Typical programs that load the OS are:

    GNU grand unified bootloader (GRUB): A multiboot specification that allows the user to choose one of several OSs
   

    NT loader (NTLDR): A boot loader for Microsoft’s Windows NT OS that usually runs from the hard drive


    Linux loader (LILO): A boot loader for Linux that generally runs from a hard drive or floppy disc


    Network interface controller (NIC): Uses a boot-loader that supports booting from a network interface such as Ether-boot or pre-boot execution environment (PXE)


Prior to bootstrap a computer is said to start with a blank main memory and an intact magnetic core memory or kernel.

The bootstrap allows the sequence of programs to load in order to initiate the OS.

The OS is the main program that manages all programs that run on a computer and performs tasks such as controlling peripheral devices like a disc drive, managing directories and files, transmitting output signals to a monitor and identifying input signals from a keyboard.

Bootstrap can also refer to as preparing early programming environments incrementally to create more complex and user-friendly programming environments.
   

CONTEXT SWITCHING

CONTEXT SWITCHING:
   
A Context switch is the switching of the CPU from one  process to another.It can Occur only in kernel mode.

A Process is an executing instance of a program.


A context is the contents of a CPU's Register and Program Counter at any point in Time.

A Register is a small amount of very fast memory inside of a CPU that is used to speed the execution  of computer programs by providing quick access.

A Program Counter is a specialized register that indicates the position of the CPU in its instruction sequence and which holds either the address of the instruction being executed or the address of the next instruction to be executed,depending on the specific system.

If we go in detail,The kernel(Core of the operating system)performing the following activities with regard to the process.

1.Suspending the progression of one process and storing the CPU's state(Context)for that process somewhere in memory.

2.Retrieving the context of the next process from memory and restoring it in the CPU's Registers.

3.Returning to the Location indicated by the Program counter(Returning the lines of code at which the process was interrupted)in order to resume the process.

Simply telling A context switch is the kernel suspending execution of one process on the CPU and resuming execution of some other process that had previously been suspended

COMPOSITE DEVICE

USB COMPOSITE DEVICE:

A USB composite device refers to a single gadget that has the  capability of providing multiple functions, for instance a combined keyboard and mouse machine. The devices will typically need a driver for full functionality.

EX:GAME CONTROLLERS.


EXAMPLE DEVICE HAVING MULTIPLE CONFIGURATIONS:

USB camera would have two configurations, one with the Video (camera), Audio (microphone) and Mass Storage features, and

another containing Video (camera), Audio (microphone) and Still Image features. As the configurations are separate the common features between configurations need to be repeated inside each independent configuration descriptor.


ISDN adapter  have two different configurations, one that presents it with a single interface of 128 Kb/s and a second that presents it with two interfaces of 64 Kb/s each.

USER MODE AND KERNEL MODE

USER MODE AND KERNEL MODE:

A processor in a computer running Windows has two different modes: user mode and kernel mode.

The processor switches between the two modes depending on what type of code is running on the processor.

Applications run in user mode, and core operating system components run in kernel mode.

 Many drivers run in kernel mode, but some drivers run in user mode.

Firstly, Intel CPUs have modes of operation called rings which specify the type of instructions and memory available to the running code. There are four rings:

    Ring 0 (also known as kernel mode) has full access to every resource. It is the mode in which the Windows kernel runs.
  
    Rings 1 and 2 can be customized with levels of access but are generally unused unless there are virtual machines running.

    Ring 3 (also known as user mode) has restricted access to resources.

The reason for this is because if all programs ran in kernel mode, they would be able to overwrite each others' memory and possibly bring down the entire system when they crashed.When you start a user-mode application, Windows creates a process for the application.

The process provides the application with a private virtual address space and a private handle table. Because an application's virtual address space is private, one application cannot alter data that belongs to another application.Each application runs in isolation, and if an application crashes, the crash is limited to that one application. Other applications and the operating system are not affected by the crash.

In addition to being private, the virtual address space of a user-mode application is limited. A processor running in user mode cannot access virtual addresses that are reserved for the operating system. Limiting the virtual address space of a user-mode application prevents the application from altering, and possibly damaging, critical operating system data.All code that runs in kernel mode shares a single virtual address space. This means that a kernel-mode driver is not isolated from other drivers and the operating system itself. If a kernel-mode driver accidentally writes to the wrong virtual address,data that belongs to the operating system or another driver could be compromised. If a kernel-mode driver crashes, the entire operating system crashes.



Switching from User Mode to Kernel Mode:

The switch from user mode to kernel mode is not done automatically by CPU. CPU is interrupted by interrupts (timers, keyboard, I/O). When interrupt occurs, CPU stops executing the current running program, switch to kernel mode, executes interrupt handler. This handler saves the state of CPU, performs its operations, restore the state and returns to user mode.